自分の環境で解消した方法:
1. ~/.ssh/known_hosts を削除
2. ~/.ssh/config へ github.com の設定を入れた
####### GitHub.com ######### Host github.com IdentityFile ~/.ssh/id_rsa__github
これだけ。
Tag: AWS
丸三日かかったけどとりあえずできた。 セキュリティ面が甘いのと設定がゴチャゴチャしているので，後ほど調整が必要。 そもそも EC2 を eu-west-1 (Irland) に置いているので，速度面での恩恵はあるのか微妙。