Can you have a look at these cloud-init logs? 
I still don't know how cloud-init works, but as far I can see, it try
to contact some URLs in order to get some data, and this task lead to
a slow down of the boot process.
url_helper.py[WARNING]: Calling [...] latest/meta-data/instance-id
(Caused by NewConnectionError [...]
I can see the same behaviour in a Scaleway instance (that it is
claimet it supports cloud-init) as well in a local KVM machine.
Is that expected?