Для единоразового подключения:

ssh -oKexAlgorithms=+diffie-hellman-group1-sha1 123.123.123.123

Для постоянного подключения, чтобы не добавлять каждый раз ключ, дописываем в файл ~/.ssh/config:

Host 123.123.123.123

KexAlgorithms +diffie-hellman-group1-sha1

На этот файл необходимо установить права 600, владельцем должен быть текущий пользователь:

chmod 600 ~/.ssh/config

chown $USER ~/.ssh/config