No problems connecting here, unless connection sharing is in use on the iPhone (I have a shortcut on the Control Center to disconnect any connected devices). If you use a VPN, try removing it for a few days & see if that helps.
The only issue I've encountered with CarPlay, and I can't guarantee it's only since 18.5, is that the whole system will disconnect occasionally, for a few seconds. CarPlay screen goes back to default for the car, then the phone reconnects & continues on as it was - audio starts back up, maps resumes directions. If I'm listening to something from the phone the audio will start glitching a few seconds prior to it disconnecting. It might do it once or twice in an hour, on a long drive - very seldom on my typical ~20 min or less drives. 2022 Chevy factory wireless CarPlay, if it matters.