index n'y changera rien. Il faut que mysql scanne toute la table quand ça commence par '%'.
Essayez l'index full text si ce sont des mots que vous cherchez. C'est un peu compliqué, il y a des mots qu'on ne peut pas chercher et il faut changer les requêtes. Typiquement
SELECT * from table where cle like '%test%' ;
deviendrait
SELECT * from table where MATCH(cle) AGAINST('test');
sans '%'