Bluetoothにもバージョン(規格)がありますが、後発機器の場合でも、複数バージョンに対応させていることが多いです。また、利用可能サービスのプロファイルも一般的に複数持っているものですが、こちらについては機器によって対応状況は様々です。

G06は Bluetooth Ver. 5.2 のため、G06側が明らかに新しいわけですが、いずれにしても、機器双方で接続可能なバージョンとプロファイルを通信し合い、確認後接続されることになるため、そのためのタイムラグが出ている可能性が考えられます。というのも、新しい規格から試行して不可の場合は順次下げてマッチングするのが通常の手順と考えられるためです。それに、Bluetoothの通信速度はそれほど速くはありませんし。

また、複数台登録している場合はペアの確認工程もあるので、他の方々も言われているように、あまり使わない機器とのペアリングを削除しておくのも有効だと思います。

◯カーナビを初期化又は接続削除
で再ペアリングしてスマホの再起動。

で、大体直ります

が、最近iPhoneでも繋がらなくなってきてるので、私はセキュリティアップデートを疑ってます。

現在の私の対策はカーナビやイヤホン、スピーカー等のペアリングを減らす、iPhoneはコレ、TORQUEはコレと分ける。

沢山Bluetoothあるので混線してるだけかも知れませんが、、、

又はスマホのバージョンに接続機器がついてきてない（要は古い）可能性もありますね。

カーナビは接続先が多く設定されていると探すのに時間がかかる気配がしますね。
私も検証中〜😀☕

その後接続が自動でされるなら接続が遅いだけ？gaṇeśa śamaさんが言われるように、古いペアリングを消されたらいかがでしょう。

実はほぼ同じ現象です。
ただ、この前水没で本体交換したばかりで、検証が足りていません。
再度ペアリングをすればそのときはいいのですが、カーオーディオを通しての通話ができたりできなかったりという状態です。
6年くらい前のKENWOODのカーナビです。

G04のBluetooth接続のペアリングを削除して
新たにG06のペアリングをすればどうでしょうか。