We consider dynamical percolation on the complete graph Kn, where each edge refreshes its state at rate μ≪1/n, and is then declared open with probability p=λ/n where λ>1. We study a random walk on this dynamical environment which jumps at rate 1/n along every open edge. We show that the mixing time of the full system exhibits cutoff at logn/μ. We do this by showing that the random walk component mixes faster than the environment process; along the way, we control the time it takes for the walk to become isolated.