I read it in the early 80's and it might not have been new then. I think it was a Del Rey published paperback but not sure.
- It was mostly one man with a mountain lion or wolf or similar apex predator as a companion.
- It was set long after whatever happened to destroy modern society.
- He knew someone (maybe old gods) had been there long ago but were gone now.
- Vaguely similar to the beginning of Battlefield Earth, but is older than that.