I was having the issue in mRemoteNG where some hosts were showing the error: “Couldn’t agree a host key algorithm (available rsa-sha2-256)” when attempting to SSH to them.

And even when ensuring all the ciphers are enabled with the Default Settings (session) -> Connection -> SSH -> Cipher, the issue was still observed.

Turns out the mRemoteNG uses its own version of Putty, called PuttyNG.exe in my case I was using an older version, hence the issue appearing, no amount of upgrading my normal Putty or updating the configurations would help.
Resolution
- Download the new version of PuTTYNG (version 0.83 at the time of writing) from https://github.com/mRemoteNG/PuTTYNG/releases
- Take a backup of the existing version, e.g. rename to PuTTYNG-old.exe for example.
- Place PuTTYNG.exe into mRemoteNG directory overwriting the existing version my directory was: c:\Program Files (x86)\mRemoteNG yours may differ.

You should now be able to log into these hosts via SSH without an issue.