Agile Requirements Traceability

I am about to start on my next project at work and we are discussing what tools and processes to use.
As you would expect (?) the project is keen to use Agile techniques and they have selected a number of standard tools and ideas that fit in along with that.
There does seem to be one exception to this which is to use a traditional requirements management tool where they will describe each requirement and detail the associated test cases.
In previous jobs where I have used Agile this has not been the case. The process I have followed before is roughly.

  1. The Product Owner defines the features on the product road map.
  2. Epics/Stories are derived from the features.
  3. An acceptance criteria is agreed by the team in the backlog refinement for each story.
  4. Tests are defined that satisfy the acceptance criteria.
    The traceability is then from the feature to the tests via the acceptance criteria in the story.
    No document mapping the requirements existed on the project in question.
    I am curious to know how other people/projects have managed requirements tracability.

Requirements Traceability is essential in a Waterfall world and if they are transitioning to Agile, they may not realise that they need to scale back on this as it is handled tacitly in the stories. The huge requirements monolith can be hard to walk away from as it can be used as a security blanket for many things.
You may find you need to go along with this approach for a while, until the Eureka moment when the realisation that this is a goal to preserve comprehensive documentation, follow process & contract negotiation is arrived at. If you put up too big of an objection, heels could be dug in.