Se tutte le query sono lente, SET NAMES può avere una priorità molto bassa sul server e quindi attendere che il carico si esaurisca. Se hai molte altre query che richiedono molto tempo per l'esecuzione, potresti provare a ottimizzarle prima.
Un'altra soluzione a questo "problema", potrebbe essere l'aggiunta di questo al tuo my.cnf sul server:
[mysqld]
init-connect = 'SET NAMES utf8'
Ciò assicura che il set di caratteri sia impostato su UTF-8 quando un client si connette, quindi il client non deve attendere il risultato di questa "interrogazione". Probabilmente vuoi disabilitare la query SET NAMES nel tuo software.
Principalmente, non mi preoccuperei troppo a meno che tu non abbia davvero MOLTI NOMI IMPOSTATI che impiegano così tanto tempo.