This sounds very like a problem we ran into recently.
Newer versions of OpenSSH don't support the ssh-rsa algorithm by default.
However, there is a workaround if you cannot upgrade your remote hosts.
All you need to do is add the following lines to the start of your .ssh/config file.
HostKeyAlgorithms +ssh-rsa
Host *
PubkeyAcceptedKeyTypes +ssh-rsa
You can replace the the
Host *
PubkeyAcceptedKeyTypes +ssh-rsa
entry with individual entries for each affected host if you want.
HTH.