I remember trying out different approaches a long time ago, and I believe that the fastest way was through "fast doubling" [0]. I applied FFT-based multiplication to it for larger numbers, and it got really really fast :)

Edit: using karatsuba like the page below is probably preferrable, though.

[0]: https://www.nayuki.io/page/fast-fibonacci-algorithms