No me podía conectar a unos servidores con una versión reciente de Debian, y descubrí que era porque las llaves ssh-rsa están en proceso de depreciación. Ugh.
Hay que agregar esto en /etc/ssh/sshd_config:
PubkeyAcceptedAlgorithms +ssh-rsa
y después reiniciar sshd, probablemente con sshd -t primero para confirmar que está bien escrito, y después con sudo killall -HUP sshd para terminar. Si estás conectado por ssh te va a sacar, y siempre existe la remota posibilidad de que no regrese el servicio, entonces ten a la mano una manera alterna de conectarte.