Not able to access hosts over SSH : no matching host key type found

This happens because in newer versions of the OpenSSH client the ssh-rsa key exchange algorithm (specifically the SHA1 signature - more info here) is no longer trusted by default.

If you are using anything newer than OpenSSH_8.8p1, OpenSSL 1.1.1l  24 Aug 2021 and are facing the following error while trying to ssh

debug1: kex: host key algorithm: (no match)
Unable to negotiate with xxx.xxx.xxx.xxx port 22: no matching host key type found. Their offer: ssh-rsa,ssh-dss

Solution

Add the following entry to ~/.ssh/config

Host *
    HostkeyAlgorithms +ssh-rsa
    PubkeyAcceptedAlgorithms +ssh-rsa

You can change the * to specific hosts too