Exactly, the Graveyard is a place to start.
But they would hardly be a prize if they were easy to find. Your best bet is to start at the graveyard and hop on your vehicle. Fly around the mountains, the valleys, and the desert near by.
Thing is, first time I hunted krayts, I spent an hour and a half in those mountains around the graveyard with my squad, looking for them. And it wasn't until we decided to give up that I found a couple in the desert on my way back to the shuttleport.
As far as the challenge of the battle, here's my opinion: you shouldn't be able to solo Krayts, but the fact of the matter is if you know how to, you can pull it off (although I think if you're using a pet it doesn't REALLY constitute soloing). At the same time though, I would rather hunt with 2-4 other experienced hunters, than go after a pair with an army of 20. With a collection of skill players with a good assortment of skills (particularly GOOD docs), everyone benefits and you actually get the sense of accomplishment.
Seriously, how rewarding is it to go and stand in a big circle and shoot them for a half hour while the munch on your pets. If you can walk away from your computer during the battle, its not an accomplishment...