I removed rsconnect and installed a previous version:
devtools::install_github("rstudio/rsconnect", ref='737cd48')
and then did rsconnect again. After that I got some errors deploying, but they were unrelated (solved that by updating my R from 3.5.1 to 3.5.2, which my packages were made for). After fixing that it worked.