I scan down a C3 for my corp every day, and I too get the feeling that relic sites spawn less often than in the past - purely subjective though, I don’t keep records.
If less people run sites then less sites respawn at random systems.
And since w-space has own constellations and regions it my take long time to respawn if sites are locked in dead systems.
I find plenty of sites in C1-3 and I don’t even get out that much. It’s mostly luck.