Solution:
This may be caused by a directive in the /etc/ssh/ssh_config file.
To allow login with RSA key you need to uncomment the line:
# IdentityFile ~/.ssh/id_rsa
to
IdentityFile ~/.ssh/id_rsa
Save the changed to ssh_config and try login again.
To diagnose the issue you can try.
ssh -vv user@hostname
If you are having a key-exchange issue then your verbose error log will show
This is solution is not mentioned on this site: