やっぱ気になるので、誰かへるぷ、ぷりーず。
友人にも試してもらったところ、やはり自宅から事務所への接続時だけ
password プロンプトが出るまで異常に時間が掛かります。
slogin -verbose して抜粋

slogin -v ほげほげ
OpenSSH_3.4p1, SSH protocols 1.5/2.0, OpenSSL 0x0090609f
****省略****
debug1: Remote protocol version 1.99, remote software version OpenSSH_3.5p1 FreeBSD-20030201
debug1: match: OpenSSH_3.5p1 FreeBSD-20030201 pat OpenSSH*
Enabling compatibility mode for protocol 2.0
debug1: Local version string SSH-2.0-OpenSSH_3.4p1
****省略****
debug1: kex_derive_keys
debug1: newkeys: mode 1
debug1: SSH2_MSG_NEWKEYS sent
debug1: waiting for SSH2_MSG_NEWKEYS
debug1: newkeys: mode 0
debug1: SSH2_MSG_NEWKEYS received
debug1: done: ssh_kex2.
debug1: send SSH2_MSG_SERVICE_REQUEST
debug1: service_accept: ssh-userauth
debug1: got SSH2_MSG_SERVICE_ACCEPT
*****しばらくたつ*****
debug1: authentications that can continue: publickey,password,keyboard-interactive
debug1: next auth method to try is publickey
debug1: try privkey: /home/USER/.ssh/identity
debug1: try privkey: /home/USER/.ssh/id_rsa
debug1: try privkey: /home/USER/.ssh/id_dsa
debug1: next auth method to try is keyboard-interactive
Password:
debug1: ssh-userauth2 successful: method keyboard-interactive