Если вы отвечаете за создание экземпляра объекта java.util.Random, вы можете вместо этого создать подкласс java.util.Random и создать собственный класс. Если какой-то другой код, который вы не можете изменить, отвечает за создание экземпляра, то вы, очевидно, не можете использовать свой собственный подкласс. Я ожидаю, что это не вариант в вашем случае.
Другая альтернатива - изменить реализацию во время загрузки класса. По сути, вы переписываете байт-код java.util.Random, чтобы сделать что-то другое, чем то, что он делает по умолчанию. Недостатком этого является то, что это повлияет на все экземпляры java.util.Random, а не только на один экземпляр, который вы, возможно, захотите изменить. С другой стороны, большая часть кода не полагается на детали реализации RNG, так что это, вероятно, не проблема.
Javassist - неплохая библиотека байт-кода. Это позволит вам переписать байт-код во время загрузки класса, чтобы вы могли, например, замените тело метода, который производит случайное число, вызовом вашего собственного класса, который реализует необходимый вам алгоритм RNG.
Вы можете написать простой файловый процессор класса, который будет запускаться для класса java.util.Random. Код может быть примерно таким:
ClassPool pool = ClassPool.getDefault();
CtClass cc = pool.get("Random"); // maybe java.util.Random
CtMethod m = cc.getDeclaredMethod("nextLong");
m.setBody("my.super.duper.RandomClass.nextLong()");
cc.writeFile();