Maybe it would be a good idea to check all the cables too and possibly replace them as you said the BIOS post screen hangs more. A hanging BIOS post screen could indicate some problem. You could check all the services that are enabled to start at startup, however I feel this wouldn't cause such an increase in boot time. Also it would be worth running a virus scan. You should also do what C12Friedman has suggested.
Has the problem been occurring for long?