Is there an efficient algorithm for determining whether or not a graph has a non-trivial automorphism?
Since you are also interested in the theory behind it, I would give you a quasi-polynomial time algorithm for your problem.

For each pair of vertices $u\neq v$ (of same degree) in $G$, we try to see if it it possible to swap $u$ and $v$.

To do this, make a copy of $G$, call it $G'$. Now, delete $u$ from $G$, delete (copy of) $v$ from $G'$.

Then, for each $w\in N(u)$ attach to it a very long path, but only polynomially long.

Then, for each (copy of) $w\in N(copy\ of\ v)$ attach to it a very long path, but only polynomially long.

All the mentioned above very long path, but polynomially long, should be of the same length.

Call Babai's algorithm on the input of this newly produced pair of graphs.

If for any pair $(u, v)$, we have a $YES$ answer from Babai's, answer $YES$ and halt.

If none returns a $YES$ answer, answer $NO$ and halt.

Clearly, attaching to all vertices in $N(u)$ and $N(v)$ forces the graph isomorphism of Babai's inner working mechanism of his algorithm to only map vertices in $N(u)$ to $N(v)$. Thus, if Babai's answer is $YES$ then we can safely plug in back $u$ and $v$ to have a non-trivial automorphism of $G$, since $G'$ is a copy of $G$.

The run-time complexity is still quasi-poly.