"Couldn't agree a key exchange algorithm" in PuTTy

I upgraded a bunch of packages on one of my servers (running Debian Testing) and now PuTTY won’t connect any more. The regular OpenSSH Client on Windows is fine though.

This is the error I’m getting:

Couldn’t agree a key exchange algorithm (available: curve25519-sha256,curve25519-sha256 @libssh.org,ecdh-sha2-nistp256,ecdh-sha2-nistp384,ecdh-sha2-nistp521,diffie-hellman-group16-sha512,diffie-hellman-group18-sha512,diffie-hellman-group14-sha256)

I guess it has to do with this changelog entry from 21st Feb (https://metadata.ftp-master.debian.org/changelogs/main/o/openssh/testing_changelog):

     - ssh(1), sshd(8): Remove diffie-hellman-group14-sha1 from the default
      key exchange proposal for both the client and server.

Any idea what settings I need to change in PuTTY to get it to work again? I’m running the latest version of PuTTY (0.73)

Don’t think there any settings in putty you could change, putty might be of been using diffie-hellman-group14-sha1, you could try the development version of putty Download PuTTY: latest development snapshot that might work which seem to be 6 months newer than 0.73.