I had this issue today, on a host that had recently had a software upgrade.
Problem: A host to which I was connecting with SSH gave this error: “Couldn’t agree a key exchange algorithm (available: Curve25519-sha256@libssh.org, ECDH-sha2-nistp521, ECDH-sha2-nistp384, ECDH-sha2-nistp256)”.
Solution: In my case I updated to a later release of Putty.exe and the issue was resolved. It appeared that the host was supporting ciphers that my putty.exe was not able to use, therefore the negotiation of a cipher failed.
