Efficient algorithms for dealing with linear algebra over the rationals
One trick I've seen elsewhere is to pick a random prime $p$, reduce everything modulo $p$, and check whether the vectors are linearly independent over $(\mathbb{Z}/p\mathbb{Z})^n$.  If $p$ is not a divisor of any of the entries of the vectors, and if $v_k$ is not in the $(\mathbb{Z}/p\mathbb{Z})^n$-span of $v_1,\dots,v_{k-1}$, then $v_k$ isn't in the $\mathbb{Q}$-span of $v_1,\dots,v_{k-1}$, either.  By picking $p$ to be large enough (larger than the largest of the vector-entries), you can be sure $p$ won't be a divisor of any of the entries.

So, this provides a pre-test you can use.  You run the pre-test first (working modulo $p$), and if it outputs "linearly independent", then you don't need to run the expensive $\mathbb{Q}$-span test; on the other hand, if it outputs "linearly dependent", then you do need to do the expensive $\mathbb{Q}$-span test (e.g., Gaussian elimination).

And, I think there's a heuristic argument that if $p$ is random and large enough, then if it's $\mathbb{Q}$-independence then with high probability (over the choice of $p$) it'll be $(\mathbb{Z}/p\mathbb{Z})^n$-independent, too.  Or something like that.  But it's just a heuristic and no guarantee that it'll work for all situations.

I hope I have this right.  I'm going from memory so I might have something backwards.  Check my logic, and try it on your situation, and see if it helps in your application or not.