はじめに

sshができなくなってしまって上記のメッセージでハングしてしまうパターンの場合の対処法です
結局理屈はわからなかったので、全ての場合に有効かどうかはわかりませんが、一応メモしておきます

経緯

あるサーバでSSHができなくなりました
原因を探るためvarboseオプションをつけて

ssh -v hoge@hogehoge.com

とやってみると、どうも

debug1: SSH2_MSG_KEXINIT sent

というメッセージのあとで反応がなくなってしまうみたいです

エラーメッセージで検索するとXENサーバだけログインできないという人がいました、で確かめてみると、私もAmazon EC2（XENを使ってる）のサーバだけログインできません

しかし、いくつか出て来る解決法はどれもダメでした

openssh-serverを再インストールするとか、ホストキーを変えるとか、ssh_configのGSSAPIAuthenticationをnoにするとか...etc.

解決

結局MTUを変更したら解決しました

sudo ifconfig eth0 mtu 1454

1454に深い意味はありません、ただMTUの変更方法調べたときにこちらを参照しただけです

そしたらアクセス出来ました！全く理屈がわからん！
ちょうどLANのルーティングを変更したところだったので、ルーティング関係だとばっかり思ったのだが、なぜMTUを変更したら直ったのかさっぱりわからない！
SSHの認証の問題なのになぜMTUが関係あるのか？なぜXENサーバだけなのか？opnesshかXENのバグ？

謎は尽きませんがとりあえず解決しましたというお話