Having implemented AKS in Python and Sage, it can get pretty slow - obviously, nowhere near a good probabilistic test even to a staggering degree of certainty. That said, most of the algorithm is very quick. It might be smart to run its basic compositeness tests, do a pseudoprime test, and only do the polynomial mod operation if the number passes.