The problem of designing budget-feasible mechanisms (BFMs) for submodular valuation functions has been extensively studied for more than a dozen years. In this NP-hard problem, a buyer aims to procure goods or services from multiple strategic sellers under a fixed budget, with the goal of maximizing a submodular valuation function. For monotone submodular valuations, the best-known approximation guarantee is 4, achieved by a randomized mechanism proposed seven years ago at WINE 2018. Since then, it has remained an open problem whether there exists a truthful BFM with an approximation guarantee better than 4—even without any computational or complexity constraints. In this paper, we break this long-standing approximation barrier for the first time by presenting truthful deterministic and randomized BFMs that achieve an approximation guarantee of 3.798 with linear-time complexity. Moreover, as our proposed BFMs are built upon novel unified algorithmic frameworks, they simultaneously achieve improved performance guarantees over state-of-the-art BFMs for non-monotone submodular valuations. To achieve the aforementioned advantages, our randomized BFM adopts the celebrated multi-round (descending) clock auction paradigm, but offers prices in only a single round to ensure linear-time complexity. It further introduces a novel pricing technique that integrates a potential function with random sampling, allowing sellers with sufficiently high quality to be randomly accepted as candidate winners. As a result, optimizing the approximation guarantee of our randomized BFM reduces to solving a non-trivial nonlinear optimization problem, which, fortunately, admits a closed-form solution. This solution also inspires a two-stage pricing technique that enables us to derandomize the mechanism, giving rise to our unified deterministic BFM. This deterministic mechanism matches the approximation guarantee of the randomized BFM for monotone submodular valuations, and achieves a slightly weaker but still superior approximation guarantee for non-monotone submodular valuations.