You can avoid checking all $\binom{n}{k}$ subsets of the rows by taking $k$ random combinations of the rows, that is, compute the determinant of
$$
\left(\sum\xi_{1i}a_i, \sum\xi_{2i} a_i, \ldots, \sum\xi_{ki}a_i\right),
$$
where $\xi_{ij}$ are independent random variables chosen from $[-N, N]\cap\mathbb{Z}$ with respect to the uniform distribution. If the $a_i$ generate $\mathbb{Z}^k$, then this matrix is essentially random, so it will most probably have a very large determinant. Repeat this procedure a few times to obtain determinants $D_1, D_2, \ldots, $, and compute the gcd of these determinants. If the $a_i$ generate $\mathbb{Z}^k$, then with high probability $(D_1, D_2)$ has only very small prime factors. If not ,compute a few more determinants, until either you can factor the result, or the sequence $(D_1,D_2), (D_1, D_2, D_3), \ldots, (D_1^, \ldots, D_k)$ seems to stabilize. In the frst case apply Gauss elimination modulo the product of all occurring prime factors, in the second case most probably the limit of the sequence equals the gcd of all $k\times k$-subdeterminants. This can again be shown by Gaus elimination. Note that while Gauss elimination is not a practical method for the original matrix, it works well modulo some integer, even if this integer is rather large.

Actually computing the probabilities occurring is difficult, as you can only prove good results if $N$ is absurdly large. However, in practice rather small values of $N$, say $10^6$ often work.