If I am reading your question correctly, then I think $A_{5}$ is an example where this fails. The automorphism group is isomorphic to $S_{5}$. The only elements of composite order in the automorphism group have order $6$ and $4$. If $\sigma$ is an automorphism of order $6$, then $\sigma^{2}$ has $3$ fixed points (by conjugation on the simple group) and $\sigma^{3}$ has $6$ fixed points, while $\sigma$ has $9$ regular  orbits. If $\tau$ is an automorphism of order $4$, then $\tau^{2}$ has $4$ fixed points, so $\tau$ has $14$ regular orbits. An automorphism of prime order $p$ has at most $6$ fixed points, so has many regular orbits.
    Note that $A_{5} \cong {\rm SL}(2,4),$ and I think there will be other cases where ${\rm SL}(2,2^{p})$ will not have this property with $p > 3$ a prime, but I have not checked (the case where $2^{p}-1$ is a Mersenne prime seems even more promising).
   It seems likely to me that it is actually rather rare to find an automorphism of a finite non-Abelian simple group which has no regular orbit.