We present and analyze a new randomized algorithm called rand-cholQR for computing tall-and-skinny QR factorizations. Using one or two random sketch matrices, it is proved that with high probability, its orthogonality error is bounded by a constant of the order of unit roundoff for any numerically full-rank matrix. An evaluation of the performance of rand-cholQR on a NVIDIA A100 GPU demonstrates that for tall-and-skinny matrices, rand-cholQR with multiple sketch matrices is nearly as fast as, or in some cases faster than, the state-of-the-art CholeskyQR2. Hence, compared to CholeskyQR2, rand-cholQR is more stable with almost no extra computational or memory cost, and therefore a superior algorithm both in theory and practice. (Joint work with Andrew Higgins, Erik Boman, and Ichitaro Yamazaki)