Ok. Vamos por partes 🙂
Siento que te robaran el otro iPhone 😟
En esta web de Apple: Si pierdes o te roban el iPhone, el iPad o el iPod touch - Soporte técnico de Apple, hay instrucciones de qué hacer, tanto si tenías activado "Buscar mi iPhone", como si no lo tenías activado.
Para que en el nuevo iPhone aparezca todo lo que tenías en el anterior, basta con que configures tu ID en el nuevo, que le restaures una copia de seguridad y que te asegures de que todo está activado en iCloud. Para esto último ve a los Ajustes del iPhone, tu ID, iCloud y comprueba que todo está activado.
Prueba y nos cuentas.
Saludos!!