A couple of points:

(1) In addition to documenting the extent of the repeatability, it would be good to have tests to prevent changes that inadvertently change the sequence of randrange values.

(2) For large arguments, cross-platform reproducibility is already a bit fragile.  For example, the _randbelow function depends on the system _log function---see the line

    k = int(1.00001 + _log(n-1, 2.0))

Now that we have the bit_length method available, it might be better to use that.