Quando un'email viene mandata dalla sorgente alla destinazione compie diversi passaggi, non è la funzione mail() che può essere lenta o meno, ma conta eventualmente il tempo che l'email impiega nel compiere questo percorso.
Se dai un'occhiata agli headers puoi renderti conto di quale o quali siano i passaggi che hanno ritardato l'invio.