From the proof of Miller-Rabin, if a number passes the Fermat primality test, it must also pass the Miller-Rabin test with the same base $a$ (a variable in the proof). And the computation complexity is the same.
The following is from the Fermat primality test:
While Carmichael numbers are substantially rarer than prime numbers,1 there are enough of them that Fermat's primality test is often not used in the above form. Instead, other more powerful extensions of the Fermat test, such as Baillie-PSW, Miller-Rabin, and Solovay-Strassen are more commonly used.
What is the benefit of Miller-Rabin and why it is said to be more powerful than the Fermat primality test?