A mi también me ha comenzado a pasar lo que comentáis. Desde hace algo más de un mes me di cuenta de que al reiniciar aparecía lo de "optimizar aplicaciones", lo consideré esporádico y no le di importancia pues apenas si reinicio el móvil.
El caso es que ahora cada vez que lo reinicio se optimiza y tarda un poco, calculo unos 3 minutos.
A ver si entre todos encontramos la causa y la solución
Un saludo