Esto se debe a la configuración con que viene, principalmente es a un sistema de autenticación que trata de usar y por eso tarda demasiado, idealmente debes deshabilitarlo desde el archivo:

cat /etc/ssh/ssh_config

Yo he deshabilitado 4 opciones, aunque se recomienda una en particular…

GSSAPIAuthentication no
GSSAPIDelegateCredentials no
GSSAPIKeyExchange no
GSSAPITrustDNS no

http://askubuntu.com/questions/246323/why-ssh-password-prompt-takes-too-long-to-appear

Como dice el comentario destacado también pueden crear un archivo con la opción destacada arriba. El archivo en cuestión debe estar en “.ssh/config”
que viene siendo un archivo en la carpeta personal del usuario ya que ahí se consultará por el perfil de usuario.

• conexion,
• demasiado,
• espera,
• lentitud,
• lento,
• ssh,
• tarda,
• tiempo