The company that we were certified through may not be able to do our surveillance audit. Is a surveillance audit required and if we choose a different company to do our audit, do we have to go through an entirely new certification?
This is new for me. I never heard of such a situation. Your contract is with a particular Certification Body. So, your organization by changing the Certification Body must restart the certification process with a new Certification Body. If I were in your shoes I would contact the Accreditation Body mentioned in your certificate to ask them for guidance.