Feltételezem próbáltad már, de azért a biztonság kedvéért ideírom:
Nekem az a tapasztalatom, hogy a telefonok egy év - két év használat után lelassulnak, és ilyenkor egy factory reset és az alkalmazások újratelepítése sokat segít.
Nem tudom az okát, lehet, ahogy te mondod, a tárhely fragmentációja vagy itt-ott valami szemét ottmarad.