SSH2_MSG_UNIMPLEMENTED packet error with PuTTY and RHEL 7.2

I recently updated one of my RHEL 7.2 servers with yum update -y. After a reboot, I tried to connect to the machine using PuTTY client, but the connection faild with the following error:

To solve the issue, open the configuration for the connection and navigate to SSH -> Kex. In the “Algorithm selection policy”, move the “Diffie-Hellman group 14” entry to the first position in the list.

Now click open and continue working …