Is there some way to test a set of koni struts and shocks off the car to see if they need to be rebuilt? Both are still quite firm but I'm sure that's not a great indicator.

Who rebuilds them/what's involved in getting them rebuilt?

There are places that have shock dynos. I don't really know much beyond that. Maybe call around your local speed shops.