Potresti provare a utilizzare una singola istruzione insert invece di eseguire un'istruzione un milione di volte:
insert into myTable
select
dbms_random.value(1, 500),
dbms_random.value(1, 500)
from
dual
connect by
level <= 1*1000*1000;
Una nota a margine:hai misurato quanto tempo è stato speso per eseguire dbms_random
e quanto tempo su effettivamente inserendo i valori?