I noticed that the compass takes a really long time to search for structures and it's pretty frustrating to deal with but the nature compass does it in seconds.

Having the same problem, the /locate command can find structures in an instant but this compass takes forever to work

Yeah, this is due to the nature of the task. With biomes it's a bit simpler, since biomes span over many chunks, you can skip some and still have an accurate result, so it doesn't take too long. With structures, you need to check every single chunk to see if the structure is present or not, so it takes quite a while. I'm working on some potential shortcuts which could speed this up.

Should be fixed in 1.3.0-forge and 2.2.0-fabric. The structure search has been significantly optimized as of these versions.