New wax required anytime you reset the toilet. You have a problem with the flange. It should be setting on top of the finished floor and it sounds like it is above the floor level. Here's the way to handle the problem. Remove the toilet and wax ring. Now set the toilet in place on the flange without wax. Now, shim the toilet as needed to level it so that it will not rock and roll. Note where the shims are and remove the toilet. Put the new wax in place and set the toilet. Before squishing the toilet into the wax, place the shims back where they were. When the toilet is set into the wax now, it should not wiggle at all. The best shims to use are from the door department, not the plumbing section. Of course the length must be trimmed. These are a composite material and will not rot. Once the toilet is firmly anchored, caulk around the base seal the space under the shims. This is both for appearance and to prevent spill water on the floor from creeping under the toilet. It is not to seal the toilet to the flange, that was done with the wax ring.