接続にっていうと語弊がありますが、Debian の OpenSSH から SSH サーバに接続しようとするとパスワード要求までに 5 秒ぐらいかかっていました。
/etc/ssh/ssh_config に書かれている以下のパラメータが原因のようです。
GSSAPIAuthentication yes
これを no にしたところ瞬時にパスワード要求がくるようになりました。
もしユーザごとに設定したい、もしくは権限がない場合は ~/.ssh/config に記述します。恥ずかしいのですが GSSAPI 認証って初めて聞きました。今のところ使ったことがないので、使うようになるまでは no でいかせてもらおうと思います。