Basic ray tracers compute one ray for each pixel (without reflection/refraction), so that this increase in time is expected, as it's roughly 256²/64²=4². This is also due to the fact that each ray is independently computed.

I don't know if sophisticated ones can save some (rays) computation by interpolating.