Бывает так, что SSH соединение до сервера устанавливается очень медленно. Можно отключить несколько опций, что приведёт к большей скорости подключения.

Выполните в консоли сервера:

sed -E 's/.(UseDNS|GSSAPIAuthentication)./\1 no/g' -i /etc/ssh/sshd_config
service sshd reload

и попробуйте подключиться и сравнить скорость авторизации.

Если подключение медленное и после этого:

ssh -vvv user@ip -p port

и наблюдайте на каком этапе подключение затормаживается.