Yes, there are plenty of games that purport to be about survival - but they're generally about survival in the sense of surviving fighting. Yes, there may be some nod to requiring food and medicine, but once you've got that sorted out, your real problem tends to be the monsters.
Both Dwarf Fortress and Minecraft do this: getting enough food to survive is pretty trivial once you know the game, and so is creating some shelter. The real challenge is dealing with monster attacks, but even that goes away with some careful organization. What you are left with in the endgame is basically a very tedious voxel editor, where instead of just placing voxels, you have to instruct dwarves to place voxels, or jump around on top of the voxels placing them one by one.
What I want is a game where you start out naked in a wilderness. Finding enough food not to starve is tough. Building even a primitive shelter is a major achievement. Starting your first fire is a joy that quickly gives way to a desperate need to keep the fire going. And once you're no longer immediately starving, the next challenge awaits: preparing for winter. You need clothes. You need medicine to treat cuts and bruises. You need stores of food. You must learn to hunt or trap animals, to distinguish herbs, to dry or otherwise preserve the food you find. You need to figure out to knap stones, how to make containers and tools.
Of course, all of these options aren't immediately available. Instead, you gain some XP for each novel experience you have: seeing some new plant, eating a different meal, the first time it rains, the first time you find a river, and so on. This encourages you to explore and experiment.
Shintolin, a web-based game, is a good step in the right direction, but it's very limited in what you can do. Don't Starve also looks very promising, but seems to take things more into a magic/fantasy direction.
Ultimately, I'm not quite sure if anyone but me would want to play this game. Me, I like a challenge, and I like games where the difficulty level isn't a wall, but rather a huge mountain. Surviving for a few days on nuts and berries would be easy, but each extra day of survival becomes harder. Perhaps, like in an old arcade game, there is no win condition: eventually, you die, of old age and exhaustion if nothing else. But how far can you make it?
(One in a series of posts about games. Follow it here.)