For those searching, I had this issue but the latest authentication method was not supported by the old version of Putty. Upgrading Putty allowed me to connect.
I downloaded the latest Putty from the official website of Putty; then it required to uninstall, so I backed up by finding the key in the registry for:
HKEY_CURRENT_USER > Software > SimonTatham
By clicking on that entry and choosing File > Export
and saved to desktop, this contains all the data and settings for Putty should something go wrong during uninstall.
Now with Putty backed up, you can uninstall Putty (CCleaner is a good option), and when it asks if you want to remove the sessions click NO, otherwise it will wipe the data, but fortunately you have the data backed up to the registry by this point.
Finally, now you can install the latest version of Putty. The latest version of Putty has the necessary authentication methods that AWS uses.