En el fichero /etc/ssh/ssh_config sustituimos la linea que pone:
GSSAPIAuthentication yes
por,
GSSAPIAuthentication no

También puede ser debido a que intente resolver los hostnames de los equipos. Para evitarlo añadimos en el /etc/ssh/sshd_config :
UseDNS no