PuTTY Fatal error: Couldn't agree on host key algorithm

You're overlooking that PuTTY and ssh (OpenSSH) are two completely separate programs. They don't share any code; they don't use any common crypto library. The ssh -Q lists don't tell you anything about what PuTTY can support.

I think the problem is that your PuTTY version is too old. Out of the signature methods offered by the server, ECDSA signatures (ecdsa-sha2-nistp256) need at least PuTTY version 0.68, while the RSA-SHA2 methods (rsa-sha2-*) will only be available in the next PuTTY release (0.75).

The cause of this is that OpenSSH servers have disabled support for the old SHA1-based ssh-rsa signature algorithm very recently (they still use the same RSA keys, but only through SHA2-based signatures), while support for DSA keys has been removed several years ago.