Se está demorando muito aparecer o pedido de password no prompt, o que pode estar fazendo o ssh ficar lento no Ubuntu são dois parametros no ssh_config
edite o arquivo /etc/ssh/ssh_config
comente as duas linhas
GSSAPIAuthentication yes
GSSAPIDelegateCredentials no
Pronto, abs.

Cara,
realmente isso traz uma lentidao no SSH.
Windows (putty) para linux, vai rapido.
Linux para linux, fica super lento.
Com essa modificacao o linux ficou um aviao na autenticacao.
Se voce puder detalhar mais essa autenticacao GSSAPI, seria bacana
Cara acho que se vc desabilitar o DNS tb pode ajudar.
Descomente UseDNS e set para “no”
UseDNS no
PARABÉNS, suas dicas são de muita valia.
Um forte abraço.
Fábio Moura