Summarizing the advices from this page, I finished up with the following:
keytool -genkeypair -keystore ~/.android/release.keystore -alias <my_alias> -storepass <my_cert_pass> -keyalg RSA
Then I got a set of questions regarding name, organization, location and password for my alias.