I think it's the default IPv6 resolve, which is bad if you don't have
the connectivity on IPv6.
(I think you should remove the IPv6 DNS entries)
I see the same here:
ssh -v
pc2.utah.geniracks.net
OpenSSH_6.0p1 Debian-4, OpenSSL 1.0.1e 11 Feb 2013
debug1: Reading configuration data /etc/ssh/ssh_config
debug1: /etc/ssh/ssh_config line 19: Applying options for *
debug1: Connecting to
pc2.utah.geniracks.net
[2011:1948:417:4:ea39:35ff:feb1:c7c] port 22.
debug1: connect to address 2011:1948:417:4:ea39:35ff:feb1:c7c port 22:
Connection timed out
debug1: Connecting to
pc2.utah.geniracks.net [155.98.34.12] port 22.
debug1: Connection established.
debug1: permanently_set_uid: 0/0
debug1: identity file /root/.ssh/id_rsa type -1
debug1: identity file /root/.ssh/id_rsa-cert type -1
debug1: identity file /root/.ssh/id_dsa type -1
debug1: identity file /root/.ssh/id_dsa-cert type -1
debug1: identity file /root/.ssh/id_ecdsa type -1
debug1: identity file /root/.ssh/id_ecdsa-cert type -1
debug1: Remote protocol version 1.99, remote software version
OpenSSH_5.4p1 FreeBSD-20100308
debug1: match: OpenSSH_5.4p1 FreeBSD-20100308 pat OpenSSH_5*
debug1: Enabling compatibility mode for protocol 2.0
debug1: Local version string SSH-2.0-OpenSSH_6.0p1 Debian-4
debug1: SSH2_MSG_KEXINIT sent
debug1: SSH2_MSG_KEXINIT received
debug1: kex: server->client aes128-ctr hmac-md5 none
debug1: kex: client->server aes128-ctr hmac-md5 none
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: Server host key: RSA 46:63:92:67:c8:75:20:4e:52:9f:2d:f6:cb:58:16:77
The authenticity of host '
pc2.utah.geniracks.net (155.98.34.12)' can't
be established.
RSA key fingerprint is 46:63:92:67:c8:75:20:4e:52:9f:2d:f6:cb:58:16:77.
Are you sure you want to continue connecting (yes/no)?
Brecht