Perdí la aplicación de verificación en dos pasos

Hola, lo que pasa es que hace poco me robaron el celular en el cual tenía la aplicación autenticador de Google el cual me arrojaba unos códigos cabe recalcar cambian cada 30 segundos y ahora que tengo nuevo dispositivo no tengo los códigos y no puede acceder a aquella aplicación porque no me aparecen los códigos ya intenté solucionar con el soporte de Google y me dicen que directamente tengo que solucionar ese problema con Facebook realmente sería de mucha ayuda si alguien me pudiera colaborar muchísimas gracias un saludo