Props to you for taking the time to test with a screen reader, as opposed to simply reading about best practices. Not enough people do this. Each screen reader does things a bit differently, so testing real behavior is important. It's also worth noting that a lot of alternative input/output devices use the same screen reader protocols, so it's not only blind people you are helping, but anyone with a non-traditional setup.

Navigation should come early in document and tab order. Screen readers have shortcuts for quickly jumping around the page and skipping things. It's a normal part of the user experience. Some screen readers and settings de-prioritize navigation elements in favor of reading headings quickly, so if you don't hear the navigation right away, it's not necessarily a bug, and there's a shortcut to get to it. The most important thing to test is whether the screen reader says what you expect it to for dynamic and complex components, such as buttons and forms, e.g. does it communicate progress, errors, and success? It's usually pretty easy to implement, but this is where many apps mess up.