I keep bluetooth off, and turn on manually when I want to use headphones. The randomization helps only from tracking the phone. But of course the headphones don't randomize.
I've done tracking as a red team, and there are GATT attributes that can fingerprint and be surprisingly accurate for some phone models.
And as you mention too. Car infotainment can be tracked as well. I've also done work with SDRs to track the Tire Pressure sensors to track most vehicles.
Unfortunately, we're in a losing battle here.