Yes -- it's a long process, and there are other contract vehicles that agencies do procurement under... so getting your GSA (even with the help of a company that does this for you): a) takes a long time, b) isn't a guarantee that you'll actually be able to be awarded for many contracts, and c) even for contracts that are under GSA, just having your GSA is about step 2 of 100
Now, if you have some particular in-house skillset that distinguishes you, turn up some opportunities and take them to one of the SIs to team on. Bring value and the opportunities to them, and you can often get into a teaming relationship with long-term benefits. Alternately, team up with an 8(a) or service disabled veteran-owned company. There are many program set-asides for those sorts of companies, so the barrier to entry in them winning government work is greatly reduced. Same basic idea -- if you can bring them some skillset they lack and help them win deals, you're probably in a better position than running from agency to agency waving your GSA schedule.
I'm sorry the company that recommended their services to you was a scam. There are several out there that offer seminars on the government procurement and capture management process that are very good. I don't want to pimp the company I used or the seminars I went to (in no way affiliated), but the outcome was that as a small company (<20 engineers) we decided that our best current path (as far as selling into the government) is to keep subbing and let our primes (ie. our partners) do the selling and bring us in for the skillset we provide that they don't have.