The Fibonacci sequence represents a sort of "worse case" for the Euclidean algorithm. This occurs because, at each step, the algorithm can subtract $F_n\,\, $ only once from $F_{n+1} \,\,$. The result is that the number of steps needed to complete the algorithm is maximal with respect to the magnitude of the two initial numbers.
Applying the algorithm to two Fibonacci numbers $F {n}\,\, $ and $F_{n+1}\,\, $, the initial step is
$$ \gcd(F_{n},F_{n+1}) = \gcd(F_{n},F_{n+1}-F_{n}) = \gcd(F_{n-1},F_{n}) $$
The second step is
$$ \gcd(F_{n-1},F_{n}) = \gcd(F_{n-1},F_{n}-F_{n-1}) = \gcd(F_{n-2},F_{n-1}) $$
and so on. Proceding in this way, we need $n $ steps to arrive to $\gcd(F_{1},F_{2}) \,\,$ and to conclude that
$$ \gcd(F_{n},F_{n+1}) = \gcd(F_1,F_2) = 1$$
that is to say, two consecutive Fibonacci numbers are necessarily coprime.
Now it is well known that the growth rate of Fibonacci numbers, with respect to $n $, is exponential. In particular, $ F_n$ is asymptotic to
$${\displaystyle \varphi ^{n}/{\sqrt {5}}} $$
where
$$\varphi=\frac {1+\sqrt {5}}{2} \approx 1.61803$$
is the golden ratio. So, for $n $ sufficiently large, we have
$$n \approx \log_{\varphi} ( \sqrt {5}\,\, F_n) \\ = \log_{\varphi} ( F_n) + \frac {\log (5)}{2 \log (\varphi)} \approx \log_{\varphi} (F_n) $$
which tells us that the number of steps required to complete the Euclidean algorithm grows in a logarithmic manner with respect to $F_n\,\, $, and is bounded by the expression above. The same result can also be written using the logarithm in base $2$ as suggested by the OP:
$$n \approx \frac { \log_{2} F_n}{\log_{2} \varphi} =K \log_{2} F_n $$
where $$K=\frac {1}{\log_{2} \varphi}=\frac {\log {2}}{\log {\varphi}} \approx 1.4404... $$
Best Answer
First note that $F_n$ is an increasing sequence. This is a simple consequence of the recurrence relation and the fact that $F_0, F_1 \geq 0$.
Now, using this, we have $$F_n = F_{n-1} + F_{n-2} \leq 2F_{n-1}.$$ It is straightforward to verify that the solution to the recurrence, $a_n = 2a_{n-1}, a_1 = 1$, is $a_n = 2^n$, which implies $F_n \leq 2^n$.
On the other side, we also have $$F_n = F_{n-1} + F_{n-2} \geq 2F_{n-2}.$$ Using similar arguments to the previous case we get $F_n \geq (\sqrt{2})^n$.
Putting everything together, $$\frac{n}{2}\log(2) = n\log(\sqrt{2}) \leq \log(F_n) \leq n\log(2).$$
In other words, $F_n = \Theta(n)$.