We do similar but sprints are somewhat flexible, more like versions. We chuck the features we want from the top of most needed, split into stories and estimate like you mentioned using brainstorming between devs and QA. Estimation happens by relatively comparing complexity of each new story compared to previously implemented stories, conservativy picking average one up if there is variance in estimates. QA is involved to determine how long it will take to test the feature or sometimes what uncertainty is there if this is even possible automatically.

In the end we have stable developer velocity metric and a really close estimate for each new version.