A faster algorithm is

F[n_] := First@NestWhile[{#[[1]] + 1, BitXor[#[[2]], 2^RandomInteger[n - 1]]} &, 
                    {0, 2^n - 1}, #[[2]] != 0 &]

where $n$ is the length of the list. But while this is a lot faster than your method, it doesn't scale well with $n$ because the expected number of steps before the process terminates increases very quickly. It is better to compute the expected value of the stopping time using analytic methods, rather than by simulation, although if the goal is to use simulation, this is the first method that came to mind.

On my machine, your algorithm takes about 30 seconds to run 10000 trials. A faster algorithm is

F[n_] := First@NestWhile[{#[[1]] + 1, BitXor[#[[2]], 2^RandomInteger[n - 1]]} &, 
                    {0, 2^n - 1}, #[[2]] != 0 &]

where $n$ is the length of the list. This takes about 12 seconds on my machine. We can make it even faster by using Compile:

G = Compile[{{n, _Integer}}, First@NestWhile[{#[[1]] + 1, BitXor[#[[2]], 
            2^RandomInteger[n - 1]]} &, {0, 2^n - 1}, #[[2]] != 0 &]]

And then the command Table[G[6], {10000}] runs in about 0.68 seconds on my system. But while this is a lot faster than your method, it doesn't scale well with $n$ because the expected number of steps before the process terminates increases very quickly. It is better to compute the expected value of the stopping time using analytic methods, rather than by simulation, although if the goal is to use simulation, this is the first method that came to mind.