TL;DR

AWSで多要素認証（Multi-Factor Authentication, MFA）を利用していて、認証に使っているスマホが壊れたら、事前にAWSに登録しているアカウントの電話番号に電話がきて復旧できる
電話認証できないと、書類での本人確認が必要で、その中に公証人による認証が必要な書類があって手間がかかるので注意
今回の教訓としては引っ越したり電話番号が変わったらすぐにAWSアカウントの登録情報を更新したほうがいい。電話番号は固定じゃなく携帯にしたほうがいい。
加えて、MFAはバックアップ（iPhoneの場合、暗号化してバックアップするとMFAもバックアップできる）やマルチデバイス（Authyとか）で使ったりできるので、対応しておいた方がいい。

MFAはバックアップやマルチデバイスでは使えないと思い込んでて（だってそれができたらMFAの意味なくない？と思っていた）調べてもいなかったのが悔やまれる。あとはQRコードをバックアップしている人もいるらしいが、それはどうなんだろうか？

参考にした記事

もしもAWSでMFAが壊れて秘密の質問に答えられなかったら
 AWSのMFAを解除するためにアメリカ大使館に足を運んだ話
 AWS の MFAキーを紛失するとやばい

経緯

2月中旬に会社が移転し住所や電話番号が変わる（が、AWSのアカウント情報を更新していなかった←これが失敗）
5月後半にAWSのMFAにしていたスマホが突然電源が入らなくなる。最近はあまりAWSを使っていなかったのでMFAのことにはまだ気づいていない
6月になってから、MFAを再設定しようと思って調べたら電話認証があることを発見
https://docs.aws.amazon.com/ja_jp/IAM/latest/UserGuide/id_credentials_mfa_lost-or-broken.html

が、ここでAWSに登録していた電話番号を更新していないことに気づく。
カスタマーサポートに電話したら書類を提出することでMFAを解除できるとのこと。

MFA解除に必要な書類

Identity Verification Form and AffidavitというAWS指定の書類
パスポートか運転免許証
AWSアカウントで登録した住所が記載されたISPや電気代の料金明細など

公証人による認証

参考にした記事にもある通り、AWS指定の書類には公証役場というところで、自分が署名したことを証明してもらう必要がある。アメリカ大使館までは行かなくてもいいが、公証役場というところで証明してもらう必要がある。開いてるのは平日9時〜17時。AWSの書類が英語なので公証役場では外国文認証というものに該当するらしい。
費用的にはアメリカ大使館の方が安いかも。上の記事によるとアメリカ大使館では50ドル、公証役場だと11,500円。

公証役場によって対応が違うようで、自分が行った公証役場では、外国文認証には予約が必要だった。和訳が必要なところもあるようだが、内容が説明できればいいとのことでそれはいらなかった。けど、自分で理解するために結局和訳したので今後の参考に公開しておく。認証自体は結構すぐ終わった。あと、書類の提出先国を伝える必要があって、アメリカなのか日本なのかAWSに問い合わせたらアメリカということだった。
外国文認証にはアポスティーユとかいう外務省がその書類を認証したという方法もあるらしいが、今回はそこまではいらなかった。

和訳

身分証明書と宣誓供述書
この書式は、公証人が有効であることを確認する必要があります。
Amazon Web Services、Inc.が提供するWebサービスへのアクセス要求、またはこれらのサービスの継続のため、私＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿(署名者)は、以下を宣言します：

1.この宣誓供述書は、以下のアカウントに関係します（* は必須です）。
アカウントのメールアドレス：＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿
AWSアカウント番号（わかっている場合）：＿＿＿＿＿＿＿＿＿＿
アカウント名 *：＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿
請求先住所 *：＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿
市、都道府県、郵便番号 *：＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿
電話番号：＿＿＿＿＿＿＿＿＿＿＿＿＿＿

追加の質問がある場合は、このメールアドレスまたは電話番号でお客様に連絡することに同意するものとします。

2.私は上記で参照したアカウントの所有者であり、多要素認証が削除されることを要求しています。

3.私は故意に虚偽または詐欺的な陳述または表明をすることは、連邦、州または地方の刑法を侵害する可能性があり、罰金または懲役またはその両方を課す可能性があることを理解しています。

署名＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿　　　　　日付＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿

以下、公証人専用
都道府県＿＿＿＿＿＿＿＿＿＿　　　　市区町村＿＿＿＿＿＿＿＿＿＿＿＿＿＿

私はこれを証明する。＿＿＿＿＿＿＿＿＿＿＿＿＿が自ら本職の面前に現れ、上記に署名された者であることが十分に証明されており、上記の目的のために行動していることを認めた。
上記を、20＿＿年の＿＿月の＿＿番目の日に証明します。
私の委任は (日付) にて期限が終了する：＿＿＿＿＿＿＿＿＿＿＿＿＿＿
＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿
（ブロック体での名前）
＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿
（公証人の署名）

そしてMFA解除

書類を3点揃えてカスタマーサポートにメールで送ったら、しばらくしてメールが来て解除されたとのこと。引っ越し＋スマホが壊れるというレアな出来事が重なったとはいえ、結局、問い合わせをはじめてから10日くらいかかった。頻繁に使ってない時期でよかった。次は絶対バックアップ作るぞ。