Możesz spróbować użyć pojedynczej instrukcji INSERT zamiast wykonywania instrukcji milion razy:
insert into myTable
select
dbms_random.value(1, 500),
dbms_random.value(1, 500)
from
dual
connect by
level <= 1*1000*1000;
Na marginesie:czy zmierzyłeś, ile czasu poświęcasz na wykonanie dbms_random
i ile czasu faktycznie wstawić wartości?