Failed to fetch Spotify repository while updating ubuntu

Given I have spotify installed on my ubuntu system When i upgrade using:

sudo apt-get update

Then I get this error:

W: An error occurred during the signature verification. The repository is not updated and the previous index files will be used. GPG error: http://repository.spotify.com stable InRelease: The following signatures couldn't be verified because the public key is not available: NO_PUBKEY 13B00F1FD2C19886

W: Failed to fetch http://repository.spotify.com/dists/stable/InRelease  

W: Some index files failed to download. They have been ignored, or old ones used instead.

This happen when somehow we'd lost the keys.

In order to solve it, I did execute the first step listed in the official installation guide, inside the section Debian / Ubuntu