Estava com esse problema em alguns servidores na minha rede local: quando tentava logar em alguma máquina, demorava muito pra pedir a senha. Encontrei a resposta:

Se você utilizar o parâmetro -v no ssh, você poderá descobrir o que é que está acontecendo, como no exemplo:

ssh -v tiago@192.168.0.1

No meu caso, a autenticação começava a ficar lenta quando chegava aqui:

debug1: Next authentication method: gssapi-with-mic
debug1: Unspecified GSS failure.  Minor code may provide more information
Cannot determine realm for numeric host address

Aí pra resolver o problema, basta desabilitar o parâmetro GSSAPIAuthentication, assim:

ssh -o GSSAPIAuthentication=no tiago@192.168.0.1

Se você preferir, pode deixar a mudança permentente, alterando o arquivo /etc/ssh/ssh_config (da máquina que você está utilizando para acessar o servidor, e não do servidor!) e descomentando (remover o #) a linha:

GSSAPIAuthentication no

Dessa forma você não vai precisar passar o parâmetro toda vez que for utilizar o SSH.

Fonte: https://forums.oracle.com/forums/thread.jspa?threadID=2393548