Yeah, what Tinkster said. A quick fix would be to possibly try a different distro. Slack is nice and fast, but arguably difficult to use. I hear good things about Vector Linux though. I think it's an easy to use version of Slackware.
Your info says you're running RedHat, which isn't really a very fast distro, especially when running Gnome. Thus another fix may be to switch window managers. You could try WindowMaker, it's nice when you learn how to use it, but I don't think it comes with RedHat anymore. Fluxbox is another good one.
Also, recompiling the kernel to better suit your machine tends to work well when you do it right. I don't know if that would cause any conflicts with the RedHat auto-update program(if you're using it) though. You can get the latest version at
www.kernel.org. Like Tinkster said, it's recomended to stay with the latest stable version. But I don't see anything wrong with trying 2.6 if you're feeling daring, or you know what you're doing. I don't think it has any features that are worth the possible trouble though.
(Edit) Yay! Me 30th post.

*crawls back into cage*