In cases of compatibility (or negotiation) problems between putty and hosts, I switch to the ssh command of Git BASH (included in Git for Windows). This has the additional advantage, that its syntax (and how to generate/add/... keys) is the same as under Linux.