Hi Sergio, thanks for looking into this! There are some fix in place to mitigate the lack of entropy you mentioned, see Snap create-key timeouts, we also use pollinate https://github.com/dustinkirkland/pollinate to seed the generator. With this in place the frequency of the timeout is much lower, but we are still being hit by it.
We have also included some debug info in order to output the entropy available when the test fails, in the log you posted above https://travis-ci.org/snapcore/snapd/builds/241031225#L3384
kernel.random.entropy_avail = 32
which is too low, despite all our efforts. Another interesting data point we have observed is that, after pointing the generator to /dev/urandom and seeding it, the timeout seems to be only happening on ubuntu-16.04-32 (this is confirmed by your log, but maybe it could be a good thing to try to reproduce the problem on other systems to be extra sure), @pedronis suggested to exclude this system from testing until we understand the root cause of the problem.