Você pode tentar usar uma única instrução de inserção em vez de executar uma instrução um milhão de vezes:
insert into myTable
select
dbms_random.value(1, 500),
dbms_random.value(1, 500)
from
dual
connect by
level <= 1*1000*1000;
Em uma observação lateral:você mediu quanto tempo é gasto na execução de
dbms_random e quanto tempo em realmente inserindo os valores? 
