There's a great answer on the topic [over on Security Stack Exchange][1] which links through to openssh's [notes on deprecating ssh-rsa][2]. It seems the problem is that the original ssh-rsa algorithm ([described in RFC 4253][3]) relied on [SHA-1][4] which is now largely defunct for cryptography: > Since 2005, SHA-1 has not been considered secure against well-funded opponents; as of 2010 many organizations have recommended its replacement. NIST formally deprecated use of SHA-1 in 2011 and disallowed its use for digital signatures in 2013. As of 2020, chosen-prefix attacks against SHA-1 are practical. But it's the signature algorithm that used SHA-1 not the key itself. ---------- > Is there any connection between key type "ssh-rsa" and allowed PK algorithms From what I can find on the topic, yes. They algorithms can be limited to a single [cipher][5] but don't typically care so much about key length. Keys are basically just [some] very large numbers. It doesn't matter how large they are, but the algorithm needs to know what to do with them. > Is there any way (I have tried ssh debug and sshd debug) to understand clearly what PK algorithms are supported on server and client like we do with ciphers? Although it's a bit cryptic this is available with openssh level 2 debug (`-vv`). You'll see `debug2: KEX algorithms: ...` and `debug2: host key algorithms: ...`. You should also see which algorithm was selected. There is also a level three debug (`-vvv`) if you want to delve deeper. [1]: https://security.stackexchange.com/questions/226131/openssh-declares-ssh-rsa-deprecated-what-do-i-do-next [2]: https://www.openssh.com/txt/release-8.2 [3]: https://tools.ietf.org/html/rfc4253#section-6.6 [4]: https://en.wikipedia.org/wiki/SHA-1 [5]: https://en.wikipedia.org/wiki/Cipher