It is the company being audited that gives the auditers the business. Its not in the interests of a dodgy company to appoint a good auditor, and its not actually in the auditors (short term) interest to uncover wrongdoing as it just means they'd lose a client.
My proposal is that you require every company to have insurance to cover the risks, making the insurers fully liable for fraud (and any other business risk that audits protect against).
Companies then don't appoint their own auditors, but the insurers do. Its in the insurers interest to make sure that any audit is effective as they're on the hook for any liability the audit misses.
This way the insentives for the auditors are aligned with the interests of the people relying on the audit (shareholders, customers, suppliers).