All I can suggest is that you attempt to isolate the culprit.
I did some research and a RAM issue is a possibility(but just a possibility) which you could test for by trying to boot with different brand/model and/or try booting with one stick only. If it is still slow try the other stick.
Also on general principles you should clear CMOS which is very easy to do, just unplug the PC and then remove the battery on the motherboard for about 10 minutes and then put it back and reboot.
If none of the above work you could try a BIOS upgrade.