Alexa doesn't matter / mean anything so don't go off that. But, you should ask for a report of new links they have acquired. Have they done anything on page? I looked at your site and the link structure is crap, I can tell that without even knowing your keywords.
About your links. The site has ~412 links, which is total shit. Most seem to come from one domain too
You could get more links paying $65 to someone here for 1,000 directory submissions. That many links could be good for local real estate terms, but they don't seem to be of quality or targeted. You need to quit working with them and find someone new.
I'm no SEO guru, but I have outranked pages with millions of links. I'm just assuming things, their links may not be indexed yet. But ask them for a report on what they have done, ask yourself if that's worth what you're paying, then go from there.
PS: if you send me your search terms I'll gauge the competition and maybe give you some more info.