Anything else to try to debug this other than 'it won' t connect'? Are you seeing any errors on the phone or on the car unit? If using a cable, do you see the AA pop-up on your phone? Have you tried on a different car? Did you use SmartSwitch to transfer settings to the new phone? If so, that may be interfering (no Idea why they do that, but this transfers paired BT devices but since you haven't actually paired the new phone, the connection just times out all the time) with it; try 'forgetting' any car unit connections from your BT list as well as WiFi (if using wireless AA).
I have had no issues on mine, but I'm not using the same car unit (tried on a 2022 Sonata with cable, and now using a Motorola Wireless AA dongle... The latter DID give me issues at first but resetting the dongle and re-adding the connections to the phone have fixed that).