The Bluetooth classic, the variant which is typically used for audio and handsfree use cases, does not support address randomization. However, Bluetooth classic device does not necessarily need to be in discoverable mode for paired device to be able to connect. Typically they are discoverable only when they are set to some kind of pairing mode.

Bluetooth LE, which is used for wearables like smart watches etc, supports address randomization and it has mechanism for finding paired devices even though the address changes. Bluetooth LE devices must advertise for other devices to be able to connect. Many headsets nowadays use classic Bluetooth for audio streaming and handsfree but in addition they use Bluetooth LE for configuring the headset through their app. That is why the headsets are often advertising all the time.

As a side note, contact tracing apps are making our phones also to advertise. Fortunately they are using address randomization properly to ensure phones can't be tracked.