The idea itself has merit, even if the implementation is questionable.
Giving bots a cryptographic identity would allow good bots to meaningfully have skin in the game and crawl with their reputation at stake. It's not a complete solution, but could be part of one. Though you can likely get the good parts from HTTP request signing alone, Cloudflare's additions to that seem fairly extraneous.
I honestly don't know what is a good solution. The status quo is certainly completely untenable. If we keep going like we are now, there won't be a web left to protect in a few years. It's worth keeping in mind that there's an opportunity cost, and even a bad solution may be preferrable to no solution at all.
... I say operating an independent web crawler.
I think the solution is some sort of PoW gateway like people are setting up now. Or a micropayments system where each page request costs a fraction of a penny.
You could combine that with some sort of IPFS/Bittorrent like system where you allow others to rehost your static content, indexed by the merkle hash of the content. That would allow users to donate bandwidth.
I really don't like the idea that you can get out of this by surveiling user agents more or distinguishing between "good" and "bad" bots which is a massive social problem.
Nobody wants proof of work, leave the block chain inspired nonsense to the crypto children
This is the original use-case for proof of work though. The idea of using proof of work to hinder spam dates back to 1997[1]
[1] https://en.wikipedia.org/wiki/Hashcash