Impiega tutto questo tempo perchè ogni volta deve scorrere tutti i record, e per ogni record deve eseguire un ciclo sulle parole da cercare.
Devi utilizzare la prarola chiave LIKE dell'sql, esempio:
codice:
select * from utenti WHERE nome LIKE '%$variabile%' OR cognome LIKE '%$variabile%';
ovviamente devi riadattarlo in modo da contemplare tutti i casi.
Altra cosa perchè utilizzare if else quanto basta solo l'if?
codice:
 if(stristr($stringa,$parola)){
} else {
   $trovato=0;
}
diventa
codice:
 if(!stristr($stringa,$parola))    
   $trovato=0;