Androidの再起動に20分もかかります‥

最善の対策は、アプリを削除→再起動、これを現象が出なくなるまで繰り返し、
元凶のアプリを探しだす。それでそのアプリをアンインストールすることだと思います。
-◇-◇-◇-
私も２ヶ月くらい前から同様の現象にあっていました。私の場合は、スマホを再起動すると、
「1個中1個のアプリを最適化しています」と表示され、大体１０～２０分、起動に時間がかかっていました。
アプリのどれかに原因があるのはほぼ間違いないだろうと思って、
アプリ側が気がついてアップデートしてくれるだろうと待っていました。

ところが、私のスマホは意図せずにたまに勝手に再起動するので
すぐに使いたいときに、それが起きると大変！
マップで場所を探して移動中にそれが起これば、予定時刻に間に合わない可能性も。
そこで、腹をくくって時間がかかっても対応することにしました。

原因が不明な場合の最後の手段は確かにスマホの初期化ですが、それをやってしまうと後の作業がとっても大変。
また元凶のアプリが不明のままで初期化しても、また同じ状態になってしまう可能性もあると考えました。

ネットには情報が殆どなかったので、元凶はメジャーでないアプリと想定し、
怪しい順に、５つくらいのアプリをまとめて削除→再起動を繰り返し行いました。
結局かなりの数のアプリを削除しましたが、あるアプリを含めて削除→再起動した後に、現象が出なくなりました。

そこで、その回に削除した５つのアプリから１つずつ、インストール→再起動して元凶のアプリを探しました。
結局、その後、現象は再現しなかったのですが、ある電卓アプリ（背景が黒）のインストールがやけに長かったし、ほかのアプリはメジャーなものだったので、たぶん、元凶は電卓アプリ（背景が黒）と推測しました。
再現しなかったのは、インストールの際に最適化が行われ、その状態で、アプリが固定化されたためと思います。
今後のAndroidのアップデートで、その電卓アプリがトラブルの元になる可能性もあると思ってたので、電卓アプリはアンインストールしました。これで終了。