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.