From what I've seen the hint timer is roughly 12 in game hours (6-7 RT minutes?). I'd suggest getting your hint on the nose while you are building your army until you have all three.

I know that the hints don't specify which wands it is for but having all three you can probably make an educated guess by the process of elimination or just by the hint itself as to which is the black rod.

Having shield and aura (along with other preps such as protection & stoneskin) should provide you with enough to at least survive while you are looking for the black.

Get the barrier attunement edge immediately. This way you have 2 options to find your barrier. You might get one that's easier than your CBL

There will be a learning curve for sure with the locations that you aren't familiar with. Use the helpfiles and wiki maps if it's an area you aren't familiar with to get you started. Eventually, you'll have seen most of the hints and will know which are for which wand and what exactly it takes to get it.

There will be tough times and easy times. I found 2 blacks, 1 amber and a sienna in an hour with a mage that wasn't in hero range recently so it can go fairly well. Just remember to keep farming your hints.

I know as a Scion you don't have a huge ally pool but there are always some you can at least hit up for information. I usually could find at least one person who'd rather be my friend that day instead of enemy, even if it was to get some info out of instead of traveling. Make use of Heralds and Nexuns!