2023 Update: Recent versions of REHL have completely disabled DES which can cause issues even when using the +ssh-rsa or +ssh-rsa. You can use the following command to enable SHA1, however, upgrading the server would be recommended.
update-crypto-policies --set DEFAULT:SHA1
Reason for it not working is some of the older weaker SSH encryption algorithms have been disabled. You can allow ssh to use it by specifying the following option.
The whole command would look like
ssh -o HostKeyAlgorithms=+ssh-dss firstname.lastname@example.org