Are you not obtaining any other supplier approval information for your products?
I'd have thought that obtaining CofAs is fairly trivial as part of the process of checking certification, obtaining specifications, verifying basic regulatory compliance etc for each ingredient?
(I say this as the person responsible for technical/regulatory/QA/QC functions in a business that handles 2000+ SKUs)
Doing things correctly often has a cost, unfortunately. I could fill up my diesel car with petrol as it's cheaper, but it doesn't make it a good idea 
I've been through similar challenges to the one that it sounds like you're facing. Two main points that helped my commercial colleagues understand a bit better:
1) The industry is moving towards ever more thorough standards. This is broadly a good thing, as safer food means fewer people harmed. Given that it's going that way, you may as well turn it to your advantage and get out ahead of it.
2) Moving quickly isn't a positive thing in and of itself - it's only a useful mechanism if it allows you to create sustainable long-term business. This can be achieved to an extent through luck, but that only goes so far - when you start cutting corner things eventually go wrong, and that has a cost either directly or in loss of repeat business opportunities.
There is a balance to be struck, and I think you will find that even here there are a lot of people who will agree that elements of the industry have lost their marbles and gone a bit OTT in some areas, but equally there is a minimum that reasonably needs to be done to ensure products are still safe and correct. Talk to your colleagues in QA, explain the predicament, and work with them to find the best balance you can for your situation. I've seen companies that turn around new products in a day - it's often too fast, things get missed, customers are unhappy (at best - at worst you're potentially harming consumers). I've also seen companies that may take 3-6 months to set up a new product due to byzantine and inflexible procedures, and lost opportunities as a result of it. Between these two extremes there is a large expanse of middle ground in which you should be able to find a sensible compromise, but it takes co-operation and understanding.
Given that your responsibility is sales, I'd also strongly recommend using this as a positive when talking with customers - yes it might take two days instead of one, but that's because you want to do it well, and that is something that is appreciated in the long term 