「アップデートを検証できません」が出てしまいます

設定アプリで一般-> iPhoneストレージと進んだところにそのiOS16.5.1があるとおもいます。

削除してからもう一度ダウンロードしてみてください。

それだと、リカバリーモードにして強制復元するしかないです。

iPhone や iPod touch をアップデートまたは復元できない場合 - Apple サポート (日本)

ストレージに空きは十分ありますか？

>他に何か方法はありますでしょうか？

現在の環境（iOSバージョン、通信経路、VPN、セキュリティソフトの有無）、試したことや確認したことを書かないと、「他の方法」がわかりませんが。

「インターネットへの接続が解除されている」は、アップルのサーバと通信できないという意味なので、この種の通信を妨害する手段やネット環境を調べる必要がありますね。