Keep in mind freezing them will not remove them from the rock- just kill them so rock would need to be cured again or all that die off will pollute your tank.
Acid dip will dissolve any life on them and should be able to go back in pretty quick. After a rinse- I was being very cautious with the recommended soak and ph testing, but that would be safest-
I use a dilute muriatic acid, actually a pretty strong mix to clean all my pumps, plumbing, rock etc etc.
you can get that at hardware stores- I buy at Home Depot or tractor supply.