We note each step in the Euclidean algorithm (EA) is just an unravelling of the recurrence backwards starting $f_{n+2}=1\cdot f_{n+1}+f_{n}$ until, after $n$ steps we reach $f_{3}=2\cdot f_{2}+0$, by which $f_{1}=f_{2}=1$ is always the $\gcd$ of adjacent Fibonacci numbers: $(f_{n+1},f_{n})=1$.
\begin{align*}
f_{n+2}&=1\cdot f_{n+1}+f_{n}\\
f_{n+1}&=1\cdot f_{n}+f_{n-1}\\
\dots\dots &\dots\dots \dots\dots\dots\\
f_{4}&=1\cdot f_{3}+f_{2}\\
f_{3}&=2\cdot f_{2}
\end{align*}
This shows the worst case scenario for the EA, since all partial quotients, bar the last, are $1$, and so it will take a maximum of $n$ steps. Indeed the least of such numbers that take a maximum of $n$ steps are adjacent Fibonacci numbers as we now show.
A theorem of Gabriel Lame shows the number of divisions required by the EA is at most $5$ times the number of digits in the smaller of the numbers. For this we need the inequality
\begin{equation}
f_{n+5}>10f_{n}\quad\text{ for $n=2,\,3,\,4,\dotsc$}\tag{1}
\end{equation}
This holds for $n=2$. For $n\geq3$
\begin{align*}
f_{n+5}&=f_{n+4}+f_{n+3}=2f_{n+3}+f_{n+2}=3f_{n+2}+2f_{n+1}\\
&=5f_{n+1}+3f_{n}=8f_{n}+5f_{n-1}
\end{align*}
Since the Fibonacci sequence is not decreasing, we have $f_{n}=f_{n-1}+f_{n-2}\leq 2f_{n-1}$, which implies $2f_{n}\leq 4f_{n-1}$. Hence $f_{n+5}=8f_{n}+5f_{n-1}>8f_{n}+4f_{n-1}\geq10f_{n}$, which implies $f_{n+5}>10f_{n}$ as required.
Now use induction for the general case:
\begin{equation}
f_{n+5k}>10^kf_{n}\quad\text{ for $n=2,\,3,\,4,\dotsc$; $k=1,\,2,\,3,\dotsc$}\tag{2}
\end{equation}
The $k=1$ case has been shown so assume true for some arbitrary $k\in\mathbb{N}$ and show for $k+1$:
\begin{align*}
f_{n+5(k+1)}&=f_{n+5+5k}=f_{n+4+5k}+f_{n+3+5k}=2f_{n+3+5k}+f_{n+2+5k}\\
&=3f_{n+2+5k}+2f_{n+1+5k}
=5f_{n+1+5k}+3f_{n+5k}\\
&=8f_{n+5k}+5f_{n-1+5k}
\end{align*}
As before we have $f_{n+5k}=f_{n-1+5k}+f_{n-2+5k}\leq 2f_{n-1+5k}$, which implies $2f_{n+5k}\leq 4f_{n-1+5k}$. Hence
\begin{align*}
f_{n+5(k+1)}&=8f_{n+5k}+5f_{n-1+5k}>8f_{n+5k}+4f_{n-1+5k}\\
&\geq10f_{n+5k}>10\cdot10^k f_{n}=10^{k+1}f_{n}
\end{align*}
by hypothesis, which implies $f_{n+5(k+1)}>10^{k+1}f_{n}$ as required to complete the induction.
Now let $a_{0}$ and $a_{1}\in\mathbb{N}$, with $a_1<a_0$, and assume it takes $j$ divisions to find $(a_0,a_1)$ by the EA:
\begin{align*}
a_{0}&=q_1\cdot a_{1}+a_{2}\\
a_{1}&=q_2\cdot a_{2}+a_{3}\\
\dots&\dots\dots\dots \dots\dots\dots\\
a_{j-2}&=q_{j-1}\cdot a_{j-1}+a_{j}\\
a_{j-1}&=q_j\cdot a_{j}
\end{align*}
Now $q_j\neq1$ since then $a_{j-1}=a_{j}$. Thus $a_{j-1}=q_j\cdot a_{j}\geq2a_{j}\geq2=f_3$. Hence $a_{j-2}\geq a_{j-1}+a_{j}\geq f_3+f_2=f_4$, $a_{j-3}\geq a_{j-2}+a_{j-1}\geq f_4+f_3=f_5$, until we reach $a_1\geq f_{j}+f_{j-1}=f_{j+1}$ and $a_1\geq f_{j+1}+f_{j}=f_{j+2}$. If $j\geq5k+1$ then $a_1\geq f_{5k+2}>10^kf_2=10^k$ by $(2)$ and so has at least $k+1$ digits. Therefore if $a_1$ has $k$ digits, then $j\leq5k$, i.e., for $a_1$ having $k$ digits, at most $5k$ divisions are required in the EA as required. These inequalities show the claim above that adjacent Fibonacci numbers $f_{j+2}$ and $f_{j+1}$ are the least such to take $j$ steps to complete the EA and if it takes $j$ iterations to find $(a_0,a_1)$ as above, then $a_0\geq f_{j+2}$ and $a_1\geq f_{j+1}$.
Binet's closed form formula for the Fibonacci numbers is
$$f_{n}=\frac{\varphi^{n}-\psi^{n}}{\varphi -\psi}=\frac{\varphi^{n}-\psi ^{n}}{\sqrt {5}}$$
where
$$\varphi =\frac{1+\sqrt {5}}{2}\approx1.6180339887\dotsc
\quad\text{and}\quad\psi =\frac{1-\sqrt {5}}{2}\approx-0.6180339887\dotsc$$
Binet's formula shows $f_n$ is asymptotic to $\varphi^n/\sqrt{5}$, which implies
\begin{equation}\label{eq:logfnsqrt5}
n\approx \log_{\varphi}(f_n\sqrt{5})\approx \log_{\varphi}f_n
\end{equation}
Hence if for integers $0<a<b$, the EA requires $n+1$ steps, then $b\geq f_{n+3}$, $a\geq f_{n+2}\geq \varphi^{n}$, then $n<\log_{\varphi}a$.
Since $f_n\sim \varphi^n/\sqrt{5}$, we also have the number of digits in $f_n$ approximately given as
\begin{equation}\label{eq:digitsfn}\log_{10}\,f_n \approx n\log_{10}\varphi\approx0.20899n
\end{equation}
where we use base $10$ as we are in decimal.
Hence if the EA takes $n+1$ steps $0.2n<\log_{10}\varphi \log_{\varphi}a =\log_{10}a$. Thus, $n<5\log_{10}a$ implying the EA always needs less than $O(\text{#digits of $a$})$ divisions.
The EA is also known as the algorithm of continued fractions, since the $q_i$ from the EA make up the partial quotients of the fraction $a_0/a_1$'s continued fraction.
Let $a_0$ and $a_1$ be as before, having $j$ linear equations obtained via the EA. For $i=1,\dotsc, j-1$ let
$$\frac{a_{i-1}}{a_{i}}=q_{i}+\frac{1}{\frac{a_i}{a_{i+1}}}\quad\text{and}\quad\frac{a_{j-1}}{a_j}=q_j$$
This gives a simple continued fraction
$$\frac{a_0}{a_1}=[q_1;\,q_2,\dotsc,q_{j-1},\,q_j]$$
where all the numerators are $1$.
Now $q_1$ is an integer, and since $a_{i-1}>a_i$, $q_2,\dotsc,q_j$ are natural numbers.
Then on applying this to the Fibonacci sequence
$$\frac{f_{n+1}}{f_{n}} =[1;\,1,\dotsc,1,\,1]\tag{3}$$
where there are $(n-1)$ $1s$ after the semicolon; note we could also write this as
$$\frac{f_{n+1}}{f_{n}} =[1;\,1,\dotsc,1,\,2]$$
with $(n-3)$ $1s$ After the semicolon and a terminating $2$ in the continued fraction for $n\geq3$. We note the number of partial quotients in the continued fraction in $(3)$, and so in general for any two integers, gives the number of steps needed in the EA.
