AirPrintプリンタが見つかりません

https://support.brother.co.jp/j/b/producttop.aspx?c=jp&lang=ja&prod=mfc695cdn
こちらですね。

本製品は、供給部品の保有期限が過ぎたため、修理対応を終了させていただきます。 なお、修理以外のお問合せについては、このままサポートを継続いたします。（2015/10/01）

となっているので修理が必要な場合は買い替えとなります。


【インクジェット プリンター】操作パネルから手動設定で無線LANに接続する方法
https://faq.brother.co.jp/app/answers/detail/a_id/10301
などを参考にルーターとプリンタの接続をやり直して見るとか。

またルーター側でプライバシーセパレーターのような機能が有効になっていないか？確認してみましょう。

それぞれの機器がWi-Fiに接続されていてもスマホ～プリンター間が正常に接続できていなければ意味がありません。
プリンターの電源を入れられるまでにどのくらいの期間が空いていたのか不明ですが、IPアドレスが変わった可能性は考えられないでしょうか？
その場合、アプリを入れ直して最初から登録しなおすのが手っ取り早い方法かもしれませんね。
スマホからハガキ印刷の場合はハガキ印刷アプリを使用することになります。
また、Webアプリを通しての印刷/登録の場合、混雑状況によってうまくいかない場合もあるようです。
・無線LANルーターの再起動
・スマホ/タブレットの再起動
・プリンターの再起動
・スマホ/タブレットのアップデート
・アプリのアップデート
・スマホ/タブレット＆プリンターのネットワークリセットをして最初から接続をやり直してみる
・プリンター本体の操作でネットワーク初期化＆スマホ/タブレットも再登録してみる

他に、ハガキ印刷されるのでしたらハガキ印刷に対応したアプリを使用されておりますでしょうか？
https://online.brother.co.jp/ot/dl/nenga/apps/


改善すると良いですね。

スマートフォン/タブレット用アプリの対応状況
↓↓↓↓↓
https://support.brother.co.jp/j/s/support/iprint_scan/?__CAMCID=GCepbmkAFw-183&__CAMSID=DoFpVbidtFe-33&__CAMVID=wotdSJbGgd&_c_d=1&_ct=1561622308870

【インクジェット プリンター】スマートフォン／タブレット端末から印刷やスキャンをする方法
↓↓↓↓↓
https://faq.brother.co.jp/app/answers/detail/a_id/10137/

スマホから印刷してみましょう(ブラザーサポートブログ)
↓↓↓↓↓
http://sblog.brother.co.jp/weblog/2015/04/post-8de4.html

【インクジェット プリンター】スマートフォン／タブレット端末から年賀状を印刷する方法
↓↓↓↓↓
https://faq.brother.co.jp/app/answers/detail/a_id/13366/

動画で見る！ かんたん無線（Wi-Fi）ガイド
↓↓↓↓↓
https://support.brother.com/g/s/id/wlan_guide/j880/wlan_jp/

https://faq.brother.co.jp/app/answers/detail/a_id/10138?a_id=13078&p=1&session=V9ERhJEo

上記は参考になるでしょうか？

その他２重ルータになっていないでしょうか？
https://naruhodo-wifi.com/double_router/