I have never seen this issue. Have you tried wiping the cache partition? Do you have any Bluetooth management apps on? Are you using a 3rd party launcher or security software? Does it occur with all Bluetooth devices?
Have you tried clearing the cache of the Bluetooth System apps by going to Settings>Apps>Show System Apps?
I don't use any MGMT apps or 3rd party apps like that. I've cleared the cache, hard reset without restoring backup. Yes, all paired devices are deleted and I have to set them up like it's the first time.
Hmmm, if the troubleshooting steps haven't helped I would recommend having your device evaluated by a certified technician. You may have two options for this depending on your location. You can either visit a local uBreakiFix location or you have the option of shipping your phone into the Samsung service center.
If it really is an issue for a note 9 to be doing that it is normal but obviously just pair it again... or get a new phone... mine (galaxy A20) does the same thing when i reset it... alot of apps close n stuff... but it is a fact dude bluetooth connection has to be reestablished on MANY different phones when they are being reset