I don't know about Monarch+, but I play on Prince and Stonehenge is very easy to get. You don't really need to make any concessions for it, and the AI doesn't go for it very early (if at all). I often build it just before or just after my first Settler, and it's almost always chopped.
I will go for Stonehenge if I think I can get it, which usually means decent production tiles + forest. Doesn't matter if I have stone, or what my traits/UB are. Because, on Prince, you don't have to give anything up for it, why not?