For a creature to have a lifespan of 5000 years on average, it needs to be far more than 1.5 times as strong/fast/smart as a human.
Accidental death rates in modern western societies is .04% with modern technology, safety and medicine. If that was the only thing that killed you, you'd have an average lifespan of only 2500 years.
So the first step is to generate a mechanism for them to actually have an average lifespan of 5000 years.
As we want to lean fantasy (these are elves), and elves live in trees, what I'd do is make the elves you see just a mobile appendage of some stationary, long-lived creature, like a tree.
An elf-tree gives birth to elves, implanted with memories, which wander the world, tend the forest, and return to dump memories and be reborn.
These elf-bodies could have a typical lifespan of 10-30 years, but the elf itself (its tree) could live for millenia. If the elf-body dies, it can grow a new one; it loses any memories collected by the elf-body that died, so that is to be avoided, but it is not fatal.
The surface protrusion of this plant could just be the flowering body, protecting it from forest fires and easy death (more like a fungus with a mushroom).
Elf-bodies are the elf-tree's seeds. They could settle down and grow a new elf-tree in a suitable spot. They could also be used as a form of information exchange, where an elf-body from one tree joins another, passing knowledge on to it.
If an elf-tree's "tree" is just the flowering body of an undergrown fungus-type creature, it could have an extremely large body. Some old elves might be the size of entire forests (like some plants are in our world), and have the ability to spawn an army of elf-body-siblings in an emergency.
Such a civilization would be quite alien to ours.
The parts we interact with -- the elf-bodies, or even the elf-homes built up around elf-trees -- would be like bacteria interacting with our skin or immune system.
Each elf-body is fully intelligent, but knows its immortality and rebirth is part and parcel of the elf-tree, and it remembers things from millenia ago (that where implanted in its fresh body).
These creatures could be vulnerable to pathogens or parasites. The elf-bodies might have a full time job keeping some kind of parasite-beatle from killing elves, for example. An invading army could burn the forest down and poison the elf itself with salt or some other chemical: their difficulty moving leaves them vulnerable.
Adventurer elf-bodies, the ones that are sent out to gather experiences, would be selected for being very reckless. They are, in a sense, disposible if expensive: the chance of death could easily be worth bringing back new interesting experiences.
The motivations of an elf-body would be highly alien to humans. Rogue elf-bodies, who aren't returning to the tree, could be a problem. And, like cancer cells in humans, rogue elf-bodies could learn how to reproduce and cause problems.
For worldbuilding purposes, humans might actually be an old cancer strain of elf-bodies. The remaining elves have figured out ways to keep the cancer away from their lands. Occasionally the elf-bodies and the humans interbreed, creating half-elves who grow like humans but may be capable of forming union with an elf-tree.