Gmail blocking emails, TXT SPF record apparently ignored

Hi all,

I’m receiving a lot of emails from my hosting provider like this:

This mail is unauthenticated, which poses a security risk
    to the XXX sender and Gmail users, and has been blocked. The sender
    must XXX authenticate with at least one of SPF or DKIM.

I already got the SPF record from my hosting provider some time ago and added it to Cloudflare.

v=spf1 a mx ipX:XX.XX.XX.X/XX ip4:XXX.XX.XX.X/XX ip4:XX.XX.XXX.X/XX ipX:XX.XXX.XX.X/XX ~all

However, emails are still getting blocked and apparently the SPF record is not provided.

I’m grateful for any tips or suggestion!

Cheers
Nico