Problem with the velocity is that we developers are really poor in estimates and the velocity is rarely accurate enough.
So what I would like to recommend is that you first check your definition of done and then start experimenting with velocity by following how many stories you get done per week. After 4 weeks calculate the average. Each week through out put should be fitted in 1 Standard deviation (Normal distribution). Make it a strict rule that only ready for prod is done done.
This contains a problem that the stories are not equal size but when we experimented with this we used shirt sizes (S, M, L) and made a rule that only S and M size stories (Small enough) where only allowed inside the sprint. Our S was max 2 days and M max 5 days. We got to a point where our through out put was 3 stories per week (Small team: 2 devs + a test expert).