解決しました。PasswordAuthenticationを無効にするとPuttyが使えないのは仕様のようです。サポートからのメールです↓

If you wish to use Putty, the PasswordAuthentication should be set to yes.

これを有効にすることで、元通りPuttyでの鍵認証ができるようになりました。
コマンドプロンプトからのSSHログインもできます。
ありがとうございました。

後学のためにred hatのおすすめ理由聞いても良いでしょうか。