Given a simple graph G, what's the quickest known way to sample one of its spanning trees at random?
I recommend Wilson's Algorithm. It is proven to select spanning trees uniformly at random. In worst case scenarios it can have complexity $n^3$, but in practical usage it often runs much faster, I believe typically $n log(n)$. I am part of a large research project at Duke and this is the algorithm we use. The current algorithm you have while faster, does not accurately sample randomly, one simple counter-example would be a star graph with an extra edge.

At the start, you have one visited vertex, and one exploring vertex (both randomly chosen). You start a random walk from the exploring vertex, until you hit a visited vertex. When the random walk makes a loop, you delete the loop from your walk, and carry on. When you hit a visited vertex, you append the vertices of your current walk to the visited vertices, and save the edges of the walk to the tree you will return. Then, you choose a new exploring vertex, and do another random walk, repeating until all vertices are visited vertices.

Here's a paper on Wilson's Algorithm and it's predecessor, the Aldous-Broder Algorithm. (which is worse in practice usually)