The test is equivalent to testing whether $3^{\frac{F_n-1}{2}} = -1\bmod F_n$. This means that you manipulate integers of size roughly $\log_2(F_n) \simeq 2^n$. By repeated squaring, you have to perform $O(\log(3^{\frac{F_n-1}{2}})) = O(F_n)$ operations on such integers, and each one has cost $O(n2^n)$ using the fastest known integer multiplication algorithm. Altogether, the complexity is $O(n2^n2^{2^n})$.

I do not know of a faster test.

The test is equivalent to testing whether $3^{\frac{F_n-1}{2}} = -1\bmod F_n$. This means that you manipulate integers of size roughly $\log_2(F_n) \simeq 2^n$. By repeated squaring, you have to perform $O(\log(\frac{F_n-1}{2})) = O(2^n)$ operations on such integers, and each one has cost $O(n2^n)$ using the fastest known integer multiplication algorithm. Altogether, the complexity is $O(n4^n)$.

I do not know of a faster test.