O site do OpenSSH tem uma página dedicada a problemas legados como este. Sugere a seguinte abordagem, no cliente :
ssh -oKexAlgorithms=+diffie-hellman-group1-sha1 123.123.123.123
ou mais permanentemente, adicionando
Host 123.123.123.123
KexAlgorithms +diffie-hellman-group1-sha1
para ~/.ssh/config
.
Isso ativará os algoritmos antigos no cliente , permitindo que ele se conecte ao servidor.