Yes, I've tried that too, but it still didn't work out. I'm really confused.Here is my solution when this occurred on my 2023 CX-5:
Main screen --> Settings --> Connectivity Settings --> Bluetooth --> Phone Connectivity Settings --> [Select your device name] --> Set Device Connection Status to "Always Enable".
Source: Owner Manual
View attachment 382730