結論

ちゃんと Recovery codes を保存したり， Fallback SMS number を保存しておきましょう．
それをしていない場合はお手上げですが， github を ssh で使用している場合，次の方法で解決する場合があります．

自分のアカウントでログインしている端末上で
$ ssh -T git@github.com verify
を実行し，その結果を github の support に送って，本人確認が取ってもらう．

確認が取れれば github の中の人が 2FA をオフにしてくれます．
その後，改めて 2FA をオンにし Recovery codes を保存したり Fallback SMS number を設定したりするのを忘れずに設定しましょう．

自分のアカウントでログインされているかを確認する

解決する場合があります ，と書いたのは「その端末でログインしているアカウントが本当に自分のアカウントの場合である」という条件が付くからです．(当たり前と言えば当たり前ですが)
自分の場合，最初2回程「送られたコード違うよ」「別のアカウントぽいよ」って返事が来てしまって???ってなったんですが，
確認したら別のアカウントでログインしてる状態になっていました．

github への ssh で，どのアカウントでログインしているかを確認するには

$ ssh -T git@github.com
Hi takesato! You've successfully authenticated, but GitHub does not provide shell access.

と， ssh -T git@github.com を実行すれば ok です．

ちなみに別のアカウントになっていた理由は ssh-agent に別の秘密鍵が登録されたままになっていた為でした．
ssh-agent が有効の場合，正しい秘密鍵を -l /path/to/id_rsa で渡しても駄目みたいです．
(1回目はそのまま，2回目は -l を付けて，3回目は ssh-agent に登録されてる鍵を削除して github に伝えたんですが3回目でやっと一致しました)

余談

なんで github にリセットして貰う事になったのか

が実は謎です．
ちょうど年末に iPhone の機種変更をし Google Authenticator が引き継がれなかったので，どうせなので新端末側で 1Password に 2FA を発行しなおして登録，年明けにその 2FA でログインして仕事を始めたはずなんですが，仕事始めて4日目位に急にログインできなくなりました．
再設定した際に 1password に保存したから複数端末でみれるし， Recovery codes 無くても良いかな…って考えていたのが甘かったという話．
Recovery codes を保存していなかったり Fallbackk SMS number を設定していない人は今すぐしましょう

不要になった公開鍵を消したい場合

なんで verify code が一致しないか調べてる時に知ったのですが，
github の管理ページから不要な鍵を消したい場合，管理ページからだと公開鍵の中身が見れないのでどれがどの公開鍵かわからない場合は，

$ ssh-keygen -l -E md5 -f ~/path/to/id_rsa.pub
2048 MD5:44:e4:c5:40:1b:36:30:c4:7a:7b:39:5b:87:2d:67:ec user@machine.local (RSA)

とやってでてくる finger print を比較するのが良いようです．