Finding a relevant SEO agency is quite difficult, but with the right things, you can make it. There are some things that you should ask your SEO company:
1. About experience
2. SEO strategy plan
3. Plan for valuable backlink
4. Tracking and reporting
5. Aware of Google algorithms
So, ask these questions to know whether the company is worth it or not.