Does it take that long if the game console is connected with any other input?

If not, you might try changing the settings or trying a different HDMI (v1.3 rated) cable.

Or, if you're running it through the receiver, try connecting it directly to the TV to see if that helps.