Finalmente cheguei à conclusão do motivo das falhas de SSH. Eu não tinha me dado conta, mas o problema surgiu depois do upgrade do Ubuntu que estou usando no laptop, para a versão 11.10 (Oneiric).
Como fui conectar em um outro servidor e tive o mesmo erro, vi que não era problema do Solaris, mas sim do cliente ssh. Então tentei uma conexão em modo de debug:
helio@shibboleet:~$ ssh -C -v slowlaris
OpenSSH_4.2p1 Debian-4.sesarge.2, OpenSSL 0.9.7m 23 Feb 2007
debug1: Reading configuration data /home/helio/.ssh/config
debug1: Reading configuration data /etc/ssh/ssh_config
debug1: Applying options for *
debug1: Connecting to slowlaris [1.2.3.103] port 22.
debug1: Connection established.
debug1: identity file /home/helio/.ssh/identity type 0
debug1: identity file /home/helio/.ssh/id_rsa type 1
debug1: identity file /home/helio/.ssh/id_dsa type 2
debug1: Remote protocol version 2.0, remote software version Sun_SSH_1.1.3
debug1: no match: Sun_SSH_1.1.3
debug1: Enabling compatibility mode for protocol 2.0
debug1: Local version string SSH-2.0-OpenSSH_4.2p1 Debian-4.sesarge.2
debug1: Unspecified GSS failure. Minor code may provide more information
Credentials cache file '/tmp/krb5cc_1000' not found
debug1: Unspecified GSS failure. Minor code may provide more information
Credentials cache file '/tmp/krb5cc_1000' not found
debug1: Unspecified GSS failure. Minor code may provide more information
debug1: Unspecified GSS failure. Minor code may provide more information
debug1: Unspecified GSS failure. Minor code may provide more information
SPNEGO cannot find mechanisms to negotiate
debug1: Offering GSSAPI proposal: (null)
debug1: SSH2_MSG_KEXINIT sent
debug1: SSH2_MSG_KEXINIT received
debug1: kex: server->client aes128-cbc hmac-md5 zlib
debug1: kex: client->server aes128-cbc hmac-md5 zlib
debug1: SSH2_MSG_KEX_DH_GEX_REQUEST(1024<1024<8192) sent
debug1: expecting SSH2_MSG_KEX_DH_GEX_GROUP
debug1: SSH2_MSG_KEX_DH_GEX_INIT sent
debug1: expecting SSH2_MSG_KEX_DH_GEX_REPLY
debug1: Host 'slowlaris' is known and matches the RSA host key.
debug1: Found key in /home/helio/.ssh/known_hosts:4
debug1: ssh_rsa_verify: signature correct
debug1: Enabling compression at level 6.
debug1: SSH2_MSG_NEWKEYS sent
debug1: expecting SSH2_MSG_NEWKEYS
debug1: SSH2_MSG_NEWKEYS received
debug1: SSH2_MSG_SERVICE_REQUEST sent
debug1: SSH2_MSG_SERVICE_ACCEPT received
debug1: Authentications that can continue: gssapi-keyex,gssapi-with-mic,publickey,password,keyboard-interactive
debug1: Next authentication method: gssapi-with-mic
debug1: Unspecified GSS failure. Minor code may provide more information
Credentials cache file '/tmp/krb5cc_1000' not found
debug1: Trying to start again
debug1: Authentications that can continue: gssapi-keyex,gssapi-with-mic,publickey,password,keyboard-interactive
debug1: Authentications that can continue: gssapi-keyex,gssapi-with-mic,publickey,password,keyboard-interactive
debug1: Authentications that can continue: gssapi-keyex,gssapi-with-mic,publickey,password,keyboard-interactive
debug1: Authentications that can continue: gssapi-keyex,gssapi-with-mic,publickey,password,keyboard-interactive
debug1: Next authentication method: publickey
debug1: Offering public key: /home/helio/.ssh/id_rsa
debug1: Authentications that can continue: gssapi-keyex,gssapi-with-mic,publickey,password,keyboard-interactive
debug1: Offering public key: /home/helio/.ssh/id_dsa
Received disconnect from 1.2.3.103: 2: Too many authentication failures for minsat
Dessa vez olhei com mais atenção a saída do comando. Notei vários erros com a mensagem "Unspecified GSS failure. Minor code may provide more information" e uma referência aos tipos de autenticação "gssapi-keyex,gssapi-with-mic,publickey,password,keyboard-interactive". Então busquei pelos erros de ssh com gssapi na Internet e... BINGO! Achei uma opção simples para desativar o mesmo, que deve ter mudado com o upgrade do openssl. Basta passar o parâmetro "-o GSSAPIAuthentication=no".
helio@shibboleet:~$ ssh -C -v -o GSSAPIAuthentication=no slowlaris
OpenSSH_4.2p1 Debian-4.sesarge.2, OpenSSL 0.9.7m 23 Feb 2007
debug1: Reading configuration data /home/helio/.ssh/config
debug1: Reading configuration data /etc/ssh/ssh_config
debug1: Applying options for *
debug1: Connecting to slowlaris [1.2.3.103] port 22.
debug1: Connection established.
debug1: identity file /home/helio/.ssh/identity type 0
debug1: identity file /home/helio/.ssh/id_rsa type 1
debug1: identity file /home/helio/.ssh/id_dsa type 2
debug1: Remote protocol version 2.0, remote software version Sun_SSH_1.1.3
debug1: no match: Sun_SSH_1.1.3
debug1: Enabling compatibility mode for protocol 2.0
debug1: Local version string SSH-2.0-OpenSSH_4.2p1 Debian-4.sesarge.2
debug1: SSH2_MSG_KEXINIT sent
debug1: SSH2_MSG_KEXINIT received
debug1: kex: server->client aes128-cbc hmac-md5 zlib
debug1: kex: client->server aes128-cbc hmac-md5 zlib
debug1: SSH2_MSG_KEX_DH_GEX_REQUEST(1024<1024<8192) sent
debug1: expecting SSH2_MSG_KEX_DH_GEX_GROUP
debug1: SSH2_MSG_KEX_DH_GEX_INIT sent
debug1: expecting SSH2_MSG_KEX_DH_GEX_REPLY
debug1: Host 'slowlaris' is known and matches the RSA host key.
debug1: Found key in /home/helio/.ssh/known_hosts:4
debug1: ssh_rsa_verify: signature correct
debug1: Enabling compression at level 6.
debug1: SSH2_MSG_NEWKEYS sent
debug1: expecting SSH2_MSG_NEWKEYS
debug1: SSH2_MSG_NEWKEYS received
debug1: SSH2_MSG_SERVICE_REQUEST sent
debug1: SSH2_MSG_SERVICE_ACCEPT received
debug1: Authentications that can continue: gssapi-keyex,gssapi-with-mic,publickey,password,keyboard-interactive
debug1: Next authentication method: publickey
debug1: Offering public key: /home/helio/.ssh/id_rsa
debug1: Authentications that can continue: gssapi-keyex,gssapi-with-mic,publickey,password,keyboard-interactive
debug1: Offering public key: /home/helio/.ssh/id_dsa
debug1: Authentications that can continue: gssapi-keyex,gssapi-with-mic,publickey,password,keyboard-interactive
debug1: Next authentication method: keyboard-interactive
Password:
debug1: Authentication succeeded (keyboard-interactive).
debug1: channel 0: new [client-session]
debug1: Entering interactive session.
debug1: Sending environment.
debug1: Sending env LANG = en_US.UTF-8
debug1: Remote: Channel 0 set: LANG=en_US.UTF-8
Last login: Tue Dec 6 11:30:56 2011 from 1.2.3.7
Oracle Corporation SunOS 5.10 Generic Patch January 2005
You have new mail.
[helio@slowlaris ~]>
Para evitar digitar essa opção em todas as conexões, simplesmente adicionei o parâmetro em ".ssh/config". E fim dos problemas.
Fonte: http://www.walkernews.net/2009/04/06/how-to-fix-scp-and-ssh-login-prompt-is-very-slow-in-linux/