As-is, the protocol supports it but makes it impossible, because device IDs are generated by each device, so you don't know the ID of the device you want to revoke. Well, unless you inspect the account file of the device you want to remove.
This could be addressed by having the device link info given in QR codes include a device ID. But then the knowledge would only go one way, ie. the phone wouldn't be able to remove the computer.
ideal solution probably involves:
Oh, I just thought of something! Device names should be generated by each client and stored on the server, but encrypted with your long-term key! That way we don't have the privacy loss of the server knowing what devices/clients you have.
This also needs support added on the server.