Get random element from C# HashSet quickly

I need to store a set of elements. What I need is functionality to

1. remove (single) elements and
2. add (sets of) elements and
3. each object should only be in the set once and
4. get a random element from the set

I chose the HashSet (C#) since it sports fast methods for removing elements (hashSet.remove(element)), adding sets (hashSet.UnionWith(anotherHashSet)) and the nature of a HashSet guarantees that there are not duplicates, so requirements 1 to 3 are taken care of.

The only way I found to get a random element is

Object object = hashSet.ElementAt(rnd.Next(hashSet.Count));

But this is very slow, since I call it once for every pixel of my map (creating a random flood fill from multiple starting points; mapsize 500x500 at the moment but I'd like to go bigger) and the hashset holds rather many items. (A quick test shows it blows up to 5752 entries before shrinking again.)

Profiling (CPU sampling) tells me my ElementAt calls take over 50%.

I realize 500x500 operations over a big hashset is no easy task, but other operations (Remove and UnionWith) are called as often as ElementAt, so the main problem seems to be the operation and not the number of calls.

I vaguely understand why getting a certain element from a HashSet is very expensive (when compared to getting it from a list or another ordered data structure, but I just want a random pick. Can it really be so hard and is there no way around it? Is there a better data structure for my purpose?

Changing everything to Lists doesn't help because now other methods become bottlenecks and it takes even longer.

Casting the HashSet to an array and pick my random element from there expectedly doesn't help because while picking a random element from an array is quick, casting the hashset to the array in the first place takes longer than running hashSet.ElementAt by itself.

If you want to understand better what I am trying to do: A link to my question and the answer.