  The mixing time of a random walk, with or without backtracking, on a random
graph generated according to the configuration model on $n$ vertices, is known
to be of order $\log n$. In this paper we investigate what happens when the
random graph becomes {\em dynamic}, namely, at each unit of time a fraction
$\alpha_n$ of the edges is randomly rewired. Under mild conditions on the
degree sequence, guaranteeing that the graph is locally tree-like, we show that
for every $\varepsilon\in(0,1)$ the $\varepsilon$-mixing time of random walk
without backtracking grows like
$\sqrt{2\log(1/\varepsilon)/\log(1/(1-\alpha_n))}$ as $n \to \infty$, provided
that $\lim_{n\to\infty} \alpha_n(\log n)^2=\infty$. The latter condition
corresponds to a regime of fast enough graph dynamics. Our proof is based on a
randomised stopping time argument, in combination with coupling techniques and
combinatorial estimates. The stopping time of interest is the first time that
the walk moves along an edge that was rewired before, which turns out to be
close to a strong stationary time.
