Really it's worse than exponential, because the size of the input is not n, it's the number of bits needed to store n i.e. log n. So as the number of bits k grow, it's growing phi^(2^k).
https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality...
As you'll see they are using the number of digits, not the value of the number, because the number of digits is the size of the input.
You can find countless examples of this in literature. So this is not a 'personally-interesting' way as you assert.