Non è che il problema è il Bluethoot del PC?
E' un classico di un Sistema Operativo purtroppo.
Installa, disinstalla e reinstalla ancora.. qualche porcheria resta che va, col tempo, a rallentare il Sistema stesso.
La cosa migliore sarebbe tenere costantemente pulito, nel limite del possibile, il Sistema Operativo.
Usare ogni Tot l'opzione di Default "Pulizia Sistema", che porta via un sacco di roba inutile.
Da Recovery anche pulire la Caches che col tempo si accumula e che, anch'essa, va a rallentare il Sistema.
Varie volte ho consigliato l'uso di una Applicazione Straordinaria per pulire il Sistema: SDMaid.
Funziona anche senza Root e, se ben settata ed usata periodicamente, mantiene costantemente pulito il Sistema Operativo.
Con questi (pochi) accorgimenti io, francamente e da oltre un anno, non formatto il Telefono che, apparentemente almeno, non dà segno alcuno di rallentamento in nulla.